[백준/C++] 27211 도넛 행성

https://www.acmicpc.net/problem/27211

 

코드

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

#define MAX 1001
#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL);
typedef pair<int, int> pi;
int n, m, arr[MAX][MAX], ans;
int dx[4] = { 1, -1, 0, 0 }, dy[4] = { 0, 0, 1, -1 };
bool visit[MAX][MAX];

void bfs(int x, int y) { 
	queue<pi> q;
	q.push({ x, y });
	visit[x][y] = true;

	while (!q.empty()) {
		int nx = q.front().first;
		int ny = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int gx = nx + dx[i];
			int gy = ny + dy[i];
			if (gx == -1) gx = n - 1;
			if (gx == n) gx = 0;
			if (gy == -1) gy = m - 1;
			if (gy == m) gy = 0;

			if (!visit[gx][gy] && arr[gx][gy] == 0) {
				visit[gx][gy] = true;
				q.push({ gx, gy });
			}
		}
	}
}

int main() {
	FASTIO;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> arr[i][j];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == 0 && !visit[i][j]) {
				bfs(i, j);
				ans++;
			}
		}
	}
	cout << ans;
	return 0;
}

설명

양끝이 연결된 구조에서 BFS를 도는 문제입니다. 따라서 gx, gy에 대해서 0~n-1, 0~m-1 을 벗어난 경우에는 적절한 값을 적용한 후, 그 값으로 방문 여부를 확인하는 등 기본적인 bfs를 수행하면 됩니다.

 

느낀 점

BFS 응용 문제입니다.