C++ / 4963 / 섬의 개수 ( 깊이 우선 탐색 )

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

문제 요약

정사각형으로 이루어져 있는 섬과 바다 지도가 주어집니다. 섬의 개수를 세는 프로그램을 작성해야합니다.

한 정사각형과 가로,  세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형입니다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 합니다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없습니다.

문제 풀이

1. while문으로 입력받는 지도 크기가 0, 0 이 아닐때 계속합니다.

2. 지도는 3차원 배열 벡터로 받는데, 지도 개수는 계속 증가 하기 때문에 매 회차 마다 벡터 사이즈를 재정의하여 증가 시켜줍니다.

3. 지도 넓이 만큼 벡터 사이즈를 초기화 해주고 지도를 입력받습니다.

4. 3차원 배열로 방문함수와 섬의 개수를 초기화 하고 ( 지도 개수, x축, y축 ) dfs탐색을 해줍니다. 현재 노드가 1인경우에 대각선 까지 탐색하여 현재 지도 범위안에 있고 1 ( 섬 )일경우 탐색해 섬의 개수를 세어줍니다.

5. 탐색이 끝난 지도는 섬의 개수를 출력하여 줍니다.

주의할 점

지도를 몇개를 입력받을지 모르기 때문에 3차원 벡터로 계속해서 사이즈를 재정의 해줘야합니다.

또한 dfs함수를 돌릴때 탐색 범위를 단순하게 w, h로 주었었는데 이는 0, 0 으로 while문에서 마지막에 정의하였기 때문에 탐색 범위는 현재 지도 배열의 범위로 해줘야합니다.

코드

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


using namespace std;


// 대각선까지 탐색
int dx[8] = { 0, 1, 1, 1, 0, -1,  -1, -1 };
int dy[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };

int w = 1, h = 1, num= 0, cnt = 0;

bool visit[51][51];
vector<vector<vector<int>>>v;

void dfs(int z,int x, int y)
{
	visit[x][y] = true;

	for (int i = 0; i < 8; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];

		// 현재 지도만큼 범위
		if (nx >= v[z].size() || nx < 0 || ny >= v[z][x].size() || ny < 0)
		{
			continue;
		}
		// 바다면 무시
		if (v[z][nx][ny] == 0)
		{
			continue;
		}
		if (!visit[nx][ny])
		{
			visit[nx][ny] = true;
			dfs(z, nx, ny);

		}
	}
}


int main()
{
	while (w > 0 && h > 0)
	{
		cin >> w >> h;
		if (w == 0 && h == 0)
		{
			break;
		}
		// 총 지도 개수 계속 증가 시킴
		v.resize(num + 1);

		// 지도 넓이 만큼 초기화
		v[num].resize(h, vector<int>(w));

		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				cin >> v[num][i][j];
			}
		}

		// 지도 개수 증가
		num++;
	}

	for (int i = 0; i < num; i++)
	{
		cnt = 0;
		// 방문 체크 초기화
		fill(&visit[0][0], &visit[0][0] + 51 * 51, false);
		for (int j = 0; j < v[i].size(); j++)
		{
			for (int k = 0; k < v[i][j].size(); k++)
			{
				if (!visit[j][k] && v[i][j][k] == 1)
				{
					dfs(i ,j, k);
					// 섬 개수 세기
					cnt++;
				}
			}

		}
		// 섬의 개수 출력
		cout << cnt << "\n";

	}
	return 0;
}

반응형

예제

1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0

결과