[210414][백준/BOJ] 4963번 섬의 개수

문제

입출력

---

풀이

dfs를 이용해서 문제를 해결할 수 있다.
일반적인 dfs 문제는 상하좌우에 접근하지만 이 문제는 대각선까지 접근할 수 있다.
따라서 dx, dy배열에 상하좌우 및 대각선 네 곳의 좌표 총 8개의 좌표를 넣으면 된다.

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

코드

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int board[52][52];
bool vis[52][52];

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(0);
	cin.tie(0);

	while (true)
	{
		int w, h;
		cin >> w >> h;

		if (w == 0 && h == 0)
			break;
		
		for (int i = 0; i < h; ++i)
			for (int j = 0; j < w; ++j)
				cin >> board[i][j];

		int num = 0;

		for (int i = 0; i < h; ++i)
		{
			for (int j = 0; j < w; ++j)
			{
				if (vis[i][j] || board[i][j] == 0) continue;
				num++;
				queue <pair<int, int>> Q;
				vis[i][j] = 1;
				Q.push({ i,j });

				while (!Q.empty())
				{
					auto 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 (vis[nx][ny] || board[nx][ny] == 0) continue;
						if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
						vis[nx][ny] = 1;
						Q.push({ nx,ny });
					}
				}
			}
		}
		cout << num << '\n';
		fill(vis[0], vis[0] + 52 * 52, 0);
	}
}