[C++] 백준 - #4963 섬의 개수

문제 설명

입력

출력

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

풀이과정

전형적인 BFS/DFS 문제이다.
다른 문제와 다른 점이라면 상하좌우가 아니라 대각선 방향까지 총 8방향을 고려해야 한다는 점이 있겠다.
이 외에 크게 신경써야 할 부분은 없었다.

소스코드

#include <bits/stdc++.h>
using namespace std;

int board[60][60];
bool vis[60][60];

#define X first
#define Y second

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


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, m;

	while (1) {

		cin >> m >> n;

		int cnt = 0;

		if (n == 0 && m == 0)
			return 0;


		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
			{
				cin >> board[i][j];
				vis[i][j] = 0;
			}


		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (vis[i][j] || board[i][j] == 0) continue;
				queue <pair<int, int>> Q;
				cnt++;
				Q.push({ i, j });

				while (!Q.empty())
				{
					pair<int, int> cur = Q.front(); Q.pop();
					for (int dir = 0; dir < 8; dir++)
					{
						int nx = cur.X + dx[dir];
						int ny = cur.Y + dy[dir];

						if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
						if (vis[nx][ny] || board[nx][ny] != 1) continue;

						vis[nx][ny] = 1;
						Q.push({ nx, ny });
					}
				}
			}
		}

			cout << cnt << "\n";
	}
}

피드백

확실히 직관적으로 해석할 수 있는 BFS문제는 크게 어려움 없이 풀 수 있다. 공식 외우듯이 외우는 것이 아니라 흐름을 이해하는게 중요한 듯 하다.