[c++/백준] 4963번: 섬의 개수

문제 링크

4963번: 섬의 개수

풀이

그래프로 푸는 문제. 난 DFS로 풀었다.

1. w와 h가 둘 다 0일 때까지 반복한다.
2. map을 초기화하고, map[i][j]가 1일 때 DFS를 호출한다.
   2-1. 그 땅을 방문했으면(visit[y][x]==1) return 0;
   2-2. 아니면 방문 처리를 하고 상하좌우, 대각선 까지 체크해준다. 범위 밖이거나 방문을 했으면 continue, 새로 방문한 땅이 1이라면 그 땅에서 다시 DFS 호출해준다.
3. 2번까지 하면 한 섬의 방문 처리는 끝난 것이므로 return 1 해주고 answer에 더해준다.

코드

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

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

vector<vector<int>> map;
vector<vector<int>> visit;

int w, h;

int DFS(int y, int x)
{
	if (visit[y][x]) return 0;
	visit[y][x] = 1;
	for (int i = 0; i < 8; i++)
	{
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue; // 범위 밖이면
		if (visit[ny][nx]) continue; // 방문했으면
		if (map[ny][nx] == 1)
		{
			DFS(ny, nx);
		}
	}
	return 1;
}

int main(void)
{
	while (1)
	{
		cin >> w >> h;
		if (w == 0 && h == 0) break;

		map.resize(h, vector<int>(w));
		visit.resize(h, vector<int>(w));

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

		int answer = 0;
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				if (map[i][j] == 1)
				{
					answer += DFS(i, j);
				}
			}
		}

		cout << answer << endl;

		map.clear();
		visit.clear();
	}
}