[S1] 2468. 안전 영역

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

2468번: 안전 영역

기본적인 bfs문제이다. 하지만, bfs가 아닌 union, find로도 해결 가능한 문제이다. 이것을 이해하는데 오랜 시간이 걸렸다.

그 방법에 대해서 알아보자.

 

방법 1. bfs

bfs를 100번 돌리면 된다. 근데 딱봐도 비효율적으로 보이지 않는가? 이것을 보완해주는 것이 union, find이다.

#include <cstdio>
#include <queue>

int main(void) {
    int N, M[100][100], R = 1; scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) scanf("%d", &M[i][j]);
    }

    int nextX[4] = { -1, 1, 0, 0 }, nextY[4] = { 0, 0, -1, 1 };
    bool V[100][100];
    std::queue<std::pair<int, int>> q;
    for (int i = 1; i <= 100; i++) {
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                if (M[j][k] <= i) V[j][k] = true;
                else V[j][k] = false;
            }
        }

        int cnt = 0;
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < N; k++) {
                if (!V[j][k]) {
                    q.push({ j, k });
                    V[j][k] = true;
                    cnt++;
                    while (!q.empty()) {
                        int x = q.front().first, y = q.front().second;
                        q.pop();
                        for (int o = 0; o < 4; o++) {
                            int nx = x + nextX[o], ny = y + nextY[o];
                            if (nx >= 0 && nx < N && ny >= 0 && ny < N && !V[nx][ny]) {
                                q.push({ nx, ny });
                                V[nx][ny] = true;
                            }
                        }
                    }
                }
            }
        }
        if (cnt > R) R = cnt;
    }
    printf("%d", R);
}

 

방법 2. union, find

자 이것을 어떻게 적용하느냐.

가장 높은 위치에서 부터 시작하는 것이다. 그리고, 다음 높이인 8을 하는데 주변에 이미 방문한 적이 있다? -1을 해주는 것이다. 이미 방문한 적이 있는 것을 어떻게 확인하는가? - union, find를 이용하는 것이다. 가장 부모에 위치해 있는 값을 이용해 이어져 있는지 확인하는 것이다. 

 

find - -1이 저장되어 있다면 그 값은 루트 노드이다. 만약 부모가 존재한다면 그 부모를 변경하면서 부모에 접근 하는 것이다. 부모를 계속해서 찾아주는 역할이다.

merge(int a, int b) - a와 b노드를 합쳐주는 역할이다.

a와 b의 부모가 다르다면 a의 부모를 b의 부모에 연결해주면 된다.

#include <cstdio>
#include <algorithm>

int parent[10000]{};
int find(int a) { return parent[a] == -1 ? a : parent[a] = find(parent[a]); }

bool merge(int a, int b) {
    int x = find(a), y = find(b);
    if (x == y) return false;
    parent[x] = y;
    return true;
}

int main(void) {
    int N; scanf("%d", &N);
    std::pair<int, int> p[10000];
    for (int i = 0; i < N * N; i++) {
        scanf("%d", &p[i].first);
        parent[i] = -1;
        p[i].second = i;
    }
    std::sort(p, p + N * N, std::greater<>());

    bool v[10000]{};
    int ans = 0, max = 0, nextX[4] = { -1, 1, 0, 0 }, nextY[4] = { 0, 0, -1, 1 };
    for (int i = 0, j = 0; i < N * N; i = j) {
        for (; j < N * N && p[i].first == p[j].first; j++);
        for (int k = i; k < j; k++) {
            ans++; v[p[k].second] = true;
            int x = p[k].second / N, y = p[k].second % N;
            for (int m = 0; m < 4; m++) {
                int nx = x + nextX[m], ny = y + nextY[m];
                if (nx >= 0 && nx < N && ny >= 0 && ny < N && v[nx * N + ny]) {
                    ans -= merge(nx * N + ny, p[k].second);
                }
            }
        }
        if (ans > max) max = ans;
    }
    printf("%d", max);
}