C++ / 2667 / 단지번호붙이기 ( 깊이 우선 탐색 )

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

문제 요약

< 그림 1 > 과 깉이 정사각형 모양의 지도가 있습니다. 1은 집이 있는 곳을, 0 은 집이 없는 곳을 나타냅니다.

< 그림 2 > 는 단지별로 번호를 붙인 것 입니다. 

지도를 입력하여 단지수를 출력하고, 각 단지에  속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성해야합니다.

문제 풀이

1. n * n 지도를 입력받습니다.

2. n * n 반복문을 만들어 노드 별로 방문하지 않았고 집인 경우에 dfs 함수를 호출하여 탐색하고, 단지 내 집의 수를 벡터로 저장하고 단지 수를 카운트 해줍니다.

3. dfs함수 내에서는 집의 수를 체크하는 변수를 증가시키고, bfs와 동일하게 4방향으로 탐색합니다.

탐색 크기가 지도를 벗어나거나 방문했거나 집이  아니면 무시하고, 방문하지 않았을 경우에 다음 노드를 탐색합니다.

4. 단지의 수를 출력합니다.

5. 단지 내의 집의 수를  저장한 벡터를 sort()함수로 오름차순 정렬하고 출력합니다.

주의할 점

깊이 우선 탐색을 이용하여 풀어야 하는 문제입니다.

노드를 탐색할때 집인 경우에만 묶어서 탐색해야 하기 때문에 

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			// 집이 있을경우 단지 탐색
			if (!visit[i][j] && v[i][j]  == 1)
			{
				dfs(i, j);
				// 단지 내 집의 수 저장
				v2.push_back(cnt);
				// 단지 수 카운트
				t++;
				// 집의 수 담을 변수 초기화
				cnt = 0;
			}
		}
	}

조건에 집인 경우에만 탐색하도록 하는것이 중요합니다.

그렇지 않으면 쓸 때 없는 노드까지 탐색해서 카운트하게 될 수 있습니다.

코드

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
vector<vector<int>>v;
vector<int> v2;
bool visit[100][100];
int n, cnt = 0, t= 0;

int dx[4] = { 0, 1, 0, -1 };
int dy[4] = { 1, 0, -1, 0 };

void dfs(int x, int y)
{
	// 집의 수 체크
	cnt++;
	visit[x][y] = true;
	for (int i = 0; i < 4; i++)
	{
		int xx = dx[i] + x;
		int yy = dy[i] + y;

		// 탐색 크기 벗어나면 continue
		if (xx >= n || xx < 0 || yy >= n || yy < 0)
		{
			continue;
		}

		// 방문했거나 집이 아니면 continue
		if (visit[xx][yy] || v[xx][yy] == 0)
		{
			continue;
		}

		// 방문 하지 않았을경우 다음 노드 탐색
		if (!visit[xx][yy])
		{
			visit[xx][yy] = true;
			dfs(xx, yy);
		}
		
	}
}
int main() 
{
	cin >> n;
	v.resize(n, vector<int>(n));
	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		for (int j = 0; j < n; j++)
		{
			v[i][j] = s[j] - '0';
		}
	}	

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			// 집이 있을경우 단지 탐색
			if (!visit[i][j] && v[i][j]  == 1)
			{
				dfs(i, j);
				// 단지 내 집의 수 저장
				v2.push_back(cnt);
				// 단지 수 카운트
				t++;
				// 집의 수 담을 변수 초기화
				cnt = 0;
			}
		}
	}

	// 단지의 수 출력
	cout << t;
	puts("");

	// 오름차순 정렬
	sort(v2.begin(), v2.end());

	// 단지내의 집의 수 출력
	for (int i = 0; i < v2.size(); i++)
	{
		cout << v2[i] << "\n";
	}
	return 0;
}

반응형

예제

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

결과