[BOJ/Gold 5] 백준 27211 도넛 행성(C++)

문제 링크

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

27211번: 도넛 행성

 

문제

준겸이는 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이라면 숲으로 막혀 있는 것이다.

출력

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

제한

•  2 ≤ N ≤ 1,000
•  2 ≤ M ≤ 1,000

예제 입력 1

5 6
1 1 1 1 1 1
1 0 0 0 1 1
1 1 1 1 0 0
1 1 1 1 0 0
1 1 1 1 1 1

예제 출력 1

2

예제 입력 2

7 8
0 0 1 1 0 0 0 0
0 1 1 1 1 0 1 0
1 1 1 1 1 1 1 1
0 1 1 1 1 1 0 0
1 1 0 0 0 1 0 0
0 1 0 0 0 1 0 1
0 0 1 1 1 1 0 0

예제 출력 2

2

직사각형 격자로 보이지만 실제로는 한 바퀴를 돌아 이동할 수 있는 도넛 모양이기 때문에, 빈 영역의 개수는 두 개이다. 

알고리즘 분류

• 그래프 탐색

풀이

비어 있는 구역이 몇 개인지를 BFS를 통해 탐색한다.

다만, 일반적인 미로 탐색과는 다르게, 한 바퀴를 돌아 이동할 수 있는 도넛 모양이다.

따라서 좌표가 0 미만이면 실제로는 N - 1 혹은 M - 1인 것이고, N 또는 M이라면 실제로는 0이 되는 것이다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 1001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M;
int MAP[MAX][MAX];
bool Visited[MAX][MAX];
int MoveY[4] = { -1,0,1,0 };
int MoveX[4] = { 0,-1,0,1 };
int Answer = 0;

void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> MAP[i][j];
        }
    }
}

void BFS(int Y, int X) {
    queue<pair<int, int> > Q;
    Visited[Y][X] = true;
    Q.push(make_pair(Y, X));
    
    while (!Q.empty()) {
        int NowY = Q.front().first;
        int NowX = Q.front().second;
        Q.pop();

        for (int i = 0; i < 4; i++) {
            int NextY = NowY + MoveY[i];
            if (NextY < 0) {
                NextY = N - 1;
            }
            else if (NextY >= N) {
                NextY = 0;
            }
            int NextX = NowX + MoveX[i];
            if (NextX < 0) {
                NextX = M - 1;
            }
            else if (NextX >= M) {
                NextX = 0;
            }
            if (!Visited[NextY][NextX] && (MAP[NextY][NextX] == 0)) {
                Visited[NextY][NextX] = true;
                Q.push(make_pair(NextY, NextX));
            }
        }
    };
}

void settings() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if ((MAP[i][j] == 0) && !Visited[i][j]) {
                BFS(i, j);
                Answer++;
            }
        }
    }
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}