[백준 2667] 단지번호붙이기 C++풀이/해결

단지번호붙이기 성공

---

시간 제한	메모리 제한	제출	제출	맞힌 사람	정답 비율
1 초	128 MB	126328	54327	34339	40.847%

 

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

 

---

풀이

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;


int map[26][26] = {0};
int check_map[25][25] = {0};
int num = 1;


bool Ischange = false;
vector<int> res;
int home[626] = { 0 }; 

void DFS(int nowI,int nowJ)
{
	if (map[nowI][nowJ] == 0 || check_map[nowI - 1][nowJ - 1] > 1) //아예 집이없거나 or 확인한적 있거나
		return;
	else
	{
		check_map[nowI - 1][nowJ - 1] = num;
		map[nowI][nowJ] = 0;
		home[num-1]++;
	

		Ischange = true;
		if (map[nowI - 1][nowJ] == 1) //상
			if(check_map[nowI - 2][nowJ-1] < 1)//한번도 check안한 곳
				DFS(nowI - 1, nowJ);
		if(map[nowI + 1][nowJ] == 1)//하
			if (check_map[nowI][nowJ-1] < 1)//한번도 check안한 곳
				DFS(nowI + 1, nowJ);
		if (map[nowI ][nowJ -1] == 1) //좌
			if (check_map[nowI -1][nowJ - 2] < 1)//한번도 check안한 곳
				DFS(nowI , nowJ - 1);
		if (map[nowI ][nowJ +1] == 1)//우
			if (check_map[nowI-1][nowJ] < 1)//한번도 check안한 곳
				DFS(nowI , nowJ+1);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	int N;
	string input = "0000000";
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> input;
		for (int j = 0; j <N; j++)
		{
			map[i][j+1] = input[j] - '0';
			}
	}
	
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			DFS(i, j);
			if (Ischange == true)
			{
				num++; 
				Ischange = false;
			}
		}
	}

	
	num--;

	cout << num<<'\n';
	for (int i = 0; i < num; i++)
		res.push_back(home[i]);

	sort(res.begin(), res.end());

	for (int i = 0; i < res.size(); i++)
		cout << res[i]<<'\n';

	
}

 

움..일단 DFS로 문제를 풀었고, 배열의 크기때문에 애를 먹었습니다.

000000000
011111110
011111110
011111110
011111110
011111110
011111110
011111110
000000000

이렇게 입력받은값들을 0이라는 벽안에 가둬둘려고했고, 이러면 따로 상하좌우 1이 있는지 검사할때 범위밖으로 나갈일이 없다고 생각을하고 map[26][26]을 했는데.. 제가 생각해놓은걸 구현할려면 [27][27] 이렇게 해야했네요 ㅎㅎㅎ;;

 

map은[26][26]으로하고, 여길 내가 전에 check했는지를 알기위해 check_map은 또 크기를[25][25]로 했더니 for문 돌릴때도 그렇고 DFS에서 if문으로 체크할때도 꽤나 애먹었습니다. 

 

그리고 입력받을때 연속된 숫자들(띄어쓰기없이)을 받기때문에 그냥 int형으로 받지않고 문자열로 받되 그 문자열의 문자 하나하나에 '0'을 빼주어 숫자로 배열에 넣어주었습니다.

 

나름 머리쓴다고 배열의 크기를 생각하다가 제꾀에 제가 넘어간듯한 느낌이었습니다. 그래도 나름 머리에 생각한걸 그대로 표현한것같아서 뿌듯하네요! :D

 

 

 

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기