[백준] 4963번 섬의 개수

문제 위치 : https://www.acmicpc.net/problem/4963

1. Approach

 

(1) BFS 탐색으로 접근한다.

 

-> 플러드필 알고리즘을 응용한다면 풀 수 있다. 그래프 이론, 영상 처리에서 많이 사용하는 알고리즘이기 때문에 짚고 넘어가는 것을 권장한다.

 

- 아이디어는 시작 좌표부터 끝 좌표까지 조건에 충족하는 좌표에서 부터 BFS를 실행한다.

- 방문한 곳들은 전부 check한다.

- BFS를 한 번 실행시킬 때 마다 섬의 개수를 1 증가시킨다. 

 

2. Source Code

 

#include <iostream>
#include <cstring>
#include <queue>
#define MAX 51
using namespace std;
int map[MAX][MAX];
bool check[MAX][MAX];

int dx[] = { 1, -1, 0, 0, 1 ,1 ,-1, -1 };
int dy[] = { 0, 0, 1, -1, 1, -1, 1, -1 };
int w, h;
void bfs(int x, int y)
{
	queue<pair<int,int>> q;
	q.push(make_pair(x, y));
	
	while (!q.empty())
	{
		int curx = q.front().first;
		int cury = q.front().second;
		q.pop();

		for (int k = 0; k < 8; k++)
		{
			int nextx = curx + dx[k];
			int nexty = cury + dy[k];

			// 범위 내, 땅인 경우, 방문하지 않은 곳만 pass
			if (nextx < 1 || nextx > h || nexty < 1 || nexty > w) continue;
			if (!map[nextx][nexty] || check[nextx][nexty]) continue;

			q.push(make_pair(nextx, nexty));
			check[nextx][nexty] = true;
		}
	}
}

int main()
{
	while (1)
	{
		cin >> w >> h;
		if (w == 0 && h == 0) break;
		int ans = 0;
		memset(check, false, sizeof(check));
		for (int i = 1; i <= h; i++)
		{
			for (int j = 1; j <= w; j++)
			{
				cin >> map[i][j];
			}
		}

		for (int i = 1; i <= h; i++)
		{
			for (int j = 1; j <= w; j++)
			{
				if (!check[i][j] && map[i][j])
				{
					bfs(i, j);
					ans++;
				}
			}
		}

		cout << ans << endl;
	}
	return 0;
}