백준] 4963 - 섬의 개수(ACM-ICPC Regionals)

시간 제한 : 1초

메모리 제한 : 128MB

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

소스코드

#include <iostream>
#include <vector>
using namespace std;
int dir[8][2] = {
{1,0},
{0,1},
{-1,0},
{0,-1},
{1,1},
{1,-1},
{-1,1},
{-1,-1}
};
int island, w, h;
vector<vector<int> > board;
vector<vector<bool> > visit;
void dfs(int y, int x)
{
	visit[y][x] = true;

	for (int i = 0; i < 8; i++)
	{
		int ny = y + dir[i][0], nx = x + dir[i][1];

		if (((ny >= 0 && ny < h) && (nx >= 0 && nx < w))
			&& (visit[ny][nx] == false && board[ny][nx] == 1))
			dfs(ny, nx);
	}
}
int main(void)
{
	while (1)
	{
		cin >> w >> h;
		if (w == 0 && h == 0)
			break;

		island = 0;
		board = vector<vector<int> >(h, vector<int>(w));
		visit = vector<vector<bool> >(h, vector<bool>(w, false));
		for (int i = 0; i < h; i++)
			for (int j = 0; j < w; j++)
				cin >> board[i][j];

		for (int y = 0; y < h; y++)
		{
			for (int x = 0; x < w; x++)
			{
				if (board[y][x] == 1 && visit[y][x] == false)
				{
					dfs(y, x);
					island++;
				}
			}
		}

		cout << island << '\n';
	}
}

Tip

나는 이것을 DFS로 풀었으나, 백준에서는 그래프 알고리즘으로 분류해놨다. 그래프를 구성하는 방식으로도 풀이가 가능할 것으로 보인다. 특정 정점을 기준으로 8방으로 건너갈 수 있는 부분을 그래프로 구성하는 식으로 풀 수도 있을 것 같다. 이런 문제는 DFS로도 어렵지 않게 풀 수 있다.