문명

백준 14868번: 문명

아이디어

상하좌우 한 칸씩 문명이 전파되는건 bfs로 어렵지 않게 구현할 수 있다. 숫자 1씩 늘리면서 몇년 지난건지도 알 수 있다. 그리고 방금 전파된 장소에서 상하좌우에 다른 문명이 있는 경우, union한다. 연도 순서대로 큐에 들어가기 때문에 1년차가 다 끝나면 2년차 시작, 2년차가 다 끝나면 3년차 시작이다. 따라서 큐에서 꺼낸 원소가 이전 원소와 연도가 다른 경우, 1년이 다 지난걸로 보고 문명이 하나가 되었나 검사한다. find로 어렵지 않게 확인할 수 있다.

코드

#include <bits/stdc++.h>

using namespace std;

const int dy[4] = {1, -1, 0, 0};
const int dx[4] = {0, 0, 1, -1};
int N, K;
int arr[2000][2000];
int p[4000000];
vector<pair<int, int>> v;

int find(int n) {
    if (p[n] < 0) return n;
    return p[n] = find(p[n]);
}

void Union(int n1, int n2) {
    n1 = find(n1);
    n2 = find(n2);
    if (n1 == n2) return;
    p[n1] += p[n2];
    p[n2] = n1;
}

bool check() {
    int np = find(N*v[0].first+v[0].second);
    for (auto p : v) {
        if (find(N*p.first+p.second) != np) return false;
    }
    return true;
}

int bfs() {
    queue<pair<int, int>> q;
    for (auto p : v) {
        q.push(p);
        arr[p.first][p.second] = 1;
    }
 
    for (auto p : v) {
        for (int i = 0; i < 4; i++) {
            int ny = p.first + dy[i];
            int nx = p.second + dx[i];
            if (ny >= N || ny < 0 || nx >= N || nx < 0) continue;
            if (arr[ny][nx] > 0) Union(N*ny+nx, N*p.first+p.second);
        }
    }

    if (check()) return 0;

    int year = 1;
    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();
        int y = cur.first;
        int x = cur.second;
        if (year != arr[y][x]) {
            if (check()) return year;
            year++;
        }
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny >= N || ny < 0 || nx >= N || nx < 0) continue;
            if (arr[ny][nx] != 0) continue;
            arr[ny][nx] = arr[y][x] + 1;
            for (int j = 0; j < 4; j++) {
                int nny = ny + dy[j];
                int nnx = nx + dx[j];
                if (nny >= N || nny < 0 || nnx >= N || nnx < 0) continue;
                if (arr[nny][nnx] > 0) {
                    Union(N*nny+nnx, N*ny+nx);
                }
            }
            q.push({ny, nx});
        }
    }
    return year;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> K;
    for (int i = 0; i < K; i++) {
        int x, y;
        cin >> x >> y;
        v.push_back({y-1, x-1});
    }
    memset(p, -1, sizeof(p));
    cout << bfs();
    return 0;
}

여담

개념만 다 알고 있으면 잘 풀 수 있을 것이다. Parent 배열의 인덱스를 N*y + x로 해서 2차원 배열을 1차원 배열로 옮겼다. pair<int, int> p[2000]도 될 것 같은데 그냥 1차원 배열로 바꾸는게 더 편하다고 생각.