BOJ 27211 : 도넛 행성

풀이 요약

BFS 를 활용한 완전 탐색

풀이 상세

1. 0 에서 $N-1$ 로 연결하는지, $N-1$ 에서 0 으로 어떻게 연결하는 지 정해야 한다. 나의 경우, 델타를 통해 다음 좌표로 이동 시, 0 보다 적으면 $N-1$ 로 $N$ 이상이면 0으로 다음좌표를 변경시켰다.

2. 방문처리는 하고 있으니, 양방향으로 연결되어도 문제는 없다.

배운점

• 배열이 보통 0 으로 초기화 되니, $MAX$ 값을 크게 정하는 경우, $N$, $M$ 을 넘어서 연산하지 않을까 했는데 생각해보니, $N$ 미만 $M$ 미만으로 탐색하니 굳이 고민할 필요가 없었던 문제였다.
• 아직까지는 확실히 자바가 편하다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> pi;
const int LEN = 1e3 + 4;
const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = {0, -1, 0, 1};
int N, M, arr[LEN][LEN];
bool visited[LEN][LEN];

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

void bfs(int i, int j) {
    queue<pi> q;
    q.push({i, j});
    while (!q.empty()) {
        pi curr = q.front();
        q.pop();
        for (int d = 0; d < 4; d++) {
            int nr = curr.first + dr[d];
            int nc = curr.second + dc[d];

            if (nr < 0) nr = N - 1;
            else if (nc < 0) nc = M - 1;
            else if (nr >= N) nr = 0;
            else if (nc >= M) nc = 0;

            if (visited[nr][nc]) continue;
            else if (arr[nr][nc] == 1) continue;
            visited[nr][nc] = true;
            q.push({nr, nc});
        }
    }
}

void output(int ans) {
    cout << ans;
}

int solve() {
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (arr[i][j] == 0 && !visited[i][j]) {
                visited[i][j] = true;
                bfs(i, j);
                cnt++;
            }
        }
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    output(solve());
    return 0;
}