[Baekjoon/C++] 27211번 - 도넛 행성

[백준] Baekjoon Online Judge

문제로 이동

 

문제

 

준겸이는 N×M칸으로 이루어진 도넛 모양의 행성에 살고 있다. 준겸이가 살고 있는 행성에는 위 그림처럼 격자 모양으로 줄이 그어져 있다. 행성의 각 칸은 숲으로 막혀 있거나, 지나갈 수 있도록 비어 있다.

준겸이는 본인의 집이 있는 위치를 기준으로 삼아 (0,0)이라고 표시하기로 했다. 준겸이는 행성 위에서 상하좌우로 걸어 다닐 수 있다. 준겸이가 오른쪽으로 한 칸 걸어가면, 위치 (0,1)에 도달할 것이다. 마찬가지로 아래로 한 칸 걸어가면, 위치 (1,0)에 도달할 것이다. 준겸이가 (0,0)에서 M칸 오른쪽으로 걸어가면, 한 바퀴를 돌아 다시 원래 자리로 되돌아오게 된다. 비슷하게 (0,0)에서 N칸 아래로 걸어가면, (0,0)으로 돌아오게 된다. 행성은 연결되어 있기 때문에, 준겸이가 (0,0)에서 왼쪽으로 한 칸 걸어가면 위치 (0,M−1)에 도달할 것이다. 마찬가지로 준겸이가 (0,0)에서 위로 한 칸 걸어가면 (N−1,0)에 도달하게 된다.

준겸이는 행성을 탐험하려고 한다. 만약 준겸이가 비어 있는 어떤 칸 A=(p1,q1)에서 시작해, 숲에 막히지 않고 비어 있는 칸 B=(p2,q2)에 도달할 수 있다면 A와 B는 같은 구역이다. 반대로, 도달할 수 없다면 A와 B는 서로 다른 구역이다. 당신은 준겸이가 탐험할 수 있는 빈 구역의 개수가 몇 개인지 출력해야 한다.

 

입력

첫 번째 줄에 N과 M이 공백을 사이에 두고 주어진다.

두 번째 줄부터 N개의 줄에 걸쳐 N×M개의 칸에 대한 정보가 주어진다. 두 번째 줄에서부터 i번째 줄에 주어지는 j번째 정수는 칸 (i−1,j−1)에 대한 정보이다. 만약 0이라면 비어 있는 것이고, 1이라면 숲으로 막혀 있는 것이다.

 

출력

탐험할 수 있는 구역의 개수를 출력한다.

 

---

풀이

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

int N, M;
int arr[1003][1003];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };

void bfs(int x, int y);

void bfs(int x, int y) {
	queue<pair<int, int>> q;
	q.push({ x, y });

	while (!q.empty()) {
		int nowx = q.front().first;
		int nowy = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = nowx + dx[i];
			int ny = nowy + dy[i];

			if (nx < 0) nx = M - 1;
			else if (nx >= M) nx = 0;

			if (ny < 0) ny = N - 1;
			else if (ny >= N) ny = 0;

			if (arr[ny][nx] == 0) {
				arr[ny][nx] = 1;
				q.push({ nx, ny });
			}
		}
	}
}

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

	cin >> N >> M;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) cin >> arr[i][j];

	int result = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (arr[i][j] == 0) {
				result++;

				bfs(j, i);
			}
		}
	}

	cout << result << '\n';

	return 0;
}

 너비우선탐색으로 문제를 풀었다.

 

void bfs(int x, int y) {
	queue<pair<int, int>> q;
	q.push({ x, y });

	while (!q.empty()) {
		int nowx = q.front().first;
		int nowy = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = nowx + dx[i];
			int ny = nowy + dy[i];
            
            		// 범위를 넘어갔을 때의 처리
			if (nx < 0) nx = M - 1;
			else if (nx >= M) nx = 0;

			if (ny < 0) ny = N - 1;
			else if (ny >= N) ny = 0;
            
            		// 비어있는 칸인 경우
			if (arr[ny][nx] == 0) {
				arr[ny][nx] = 1;
				q.push({ nx, ny });
			}
		}
	}
}

 너비우선탐색을 하는 함수이다. 문제를 읽어보면 좌표가 0 미만이 되거나 입력 받은 범위를 초과하게 되었을 때 좌표의 변화가 발생하므로 이를 if문으로 구현하였다.