[백준] BOJ 17472 : 다리 만들기 2

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

17472번: 다리 만들기 2

문제를 읽어보면 조건들은 아래와 같습니다.

1. 땅과 바다로 구분된 지도가 주어집니다. 상하좌우로 인접한 땅은 하나의 섬으로 봅니다.
2. 목표는 섬을 모두 잇는 겁니다. 두 섬은 바다에 다리를 건설해서 이을 수가 있습니다.
3. 다리는 바다에만 놓을 수 있습니다. 그리고 다리의 길이는 다리가 격자에서 차지하는 수로, 2 이상이 되어야 합니다.
4. 또한, 다리는 중간에 방향이 바뀌면 안됩니다. (즉, 일직선으로 이어져야 합니다.)
5. 그렇다면 모든 섬을 이을 때, 모든 다리의 길이들의 합의 최솟값을 출력해야합니다.

일단 저는 문제를 처음 읽을 때, "각 땅이 어느 섬에 속해있는가?"와 "섬들간의 다리의 길이들을 어떻게 구할 것인가?"를 어떻게 구할지부터 생각했습니다. 일단, 각 땅이 어느 섬에 속해있는지는 BFS를 활용해서 O(NM)만에 구할수가 있습니다. 또한, BFS를 돌리면서 겸사겸사 섬의 개수도 알 수가 있지요.

 

섬의 개수와 각 땅이 어느 섬에 속해있는지를 파악했으면은 섬들간의 다리의 길이들을 구해야 합니다. 이때, 저는 N*M의 범위가 상당히 작다는 것을 주의깊이 봤습니다. 제가 세운 알고리즘은 다음과 같았습니다.

 

1. 모든 칸을 탐색한다.
2. 만약에 칸이 땅이라면 해당 땅으로부터 상하좌우로 계속 뻗어본다. 이는 땅을 만나거나 지도의 끝에 닿을 때까지 진행한다.
3. 땅을 만났다면 해당 땅은 만난 땅과의 다리를 놓을 수가 있다. 다만, 다리의 길이가 2가 아니라면 무시한다.

이렇게 Bruteforcing을 해도 가능한 이유는, N*M이 100 이하이기 때문입니다. 위 알고리즘의 시간복잡도를 따져보면 모든 칸을 도는데 O(NM), 각 칸에서 상하좌우로 뻗는데 O(N+M)이므로 총 시간복잡도는 O(NM(N+M))이 됩니다. 충분히 시간내에 돌아가는 범위입니다. 그래서 각 섬들간의 놓을 수 있는 모든 다리들을 파악하는 건 Bruteforcing으로 해결했습니다.

 

이후에 모든 섬들이 이어질 때, 다리의 길이들의 총합의 최솟값은 MST 알고리즘을 통해서 구했습니다. 다리의 갯수가 E라고 한다면 시간복잡도는 O(ElogE)입니다. E가 100*100 미만일 것이므로 충분히 돌아갑니다. 그리고 마지막에 연결되지 않은 섬이 있는지 확인하는 건 MST 알고리즘을 사용했을 때 겸사겸사 구현한 DSU로 찾았습니다.

 

그래서 총 시간복잡도는 O(NM+NM(N+M)+ElogE)입니다. 코드는 아래와 같습니다만, 제가 작성한 코드에서는 다리의 길이가 2 미만일 때 무시하는 것을 MST 알고리즘 구현시에 판단하도록 했습니다.

#include<bits/stdc++.h>
#define ll long long
using namespace std;
// Default

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>
// PBDS

int dy[4] = {1,-1,0,0};
int dx[4] = {0,0,1,-1};

ll p[100];

ll f(ll n){
    if(p[n] == n) return n;
    return p[n] = f(p[n]);
}

bool u(ll a, ll b){
    ll pa = f(a), pb = f(b);
    if(pa == pb) return false;
    p[pa] = pb;
    return true;
}
// Kruskal Algorithm을 위한 DSU

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll N, M;
    cin >> N >> M;

    vector<vector<ll>> m(N, vector<ll>(M));
    vector<vector<ll>> vis(N, vector<ll>(M, -1));
    
    for(int i =0; i<N; ++i)
        for(int j =0; j<M;++j)
            cin >> m[i][j];

    ll g = 0;
    for(int i =0; i<N; ++i){
        for(int j =0; j<M; ++j){
            if(vis[i][j] != -1 || !m[i][j]) continue;
            vis[i][j] = g;
            deque<pair<ll,ll>> q;
            q.push_back({i,j});
            while(!q.empty()){
                ll y, x;
                tie(y,x) = q.front();
                q.pop_front();
                vis[i][j] = g;
                for(int k =0;k<4; ++k){
                    ll n_y = y+dy[k], n_x = x+dx[k];
                    if(n_y < 0 || n_y >= N || n_x < 0 || n_x >= M) continue;
                    if(!m[n_y][n_x] || vis[n_y][n_x] != -1) continue;
                    vis[n_y][n_x] = g;
                    q.push_back({n_y,n_x});
                }
            }
            ++g;
        }
    } // BFS로 각 섬들의 그룹을 파악

    priority_queue<tuple<ll,ll,ll>> pq;
    ll ans = 0;

    for(int i =0; i<N; ++i){
        for(int j =0; j<M; ++j){
            if(m[i][j]){
                for(int k =0; k<4; ++k){
                    ll y = i, x = j;
                    ll n_y = i, n_x = j;
                    while(true){    
                        n_y = y+dy[k], n_x = x+dx[k];
                        if(n_y < 0 || n_y >= N || n_x < 0 || n_x >= M) break;
                        if(vis[n_y][n_x] != -1){
                            pq.push({-(abs(n_y-i + n_x-j)-1), vis[i][j], vis[n_y][n_x]});
                            break;
                        } // 갔는데 다른 섬이 있다면 거기서 스톱
                        y = n_y, x = n_x;
                    }
                }
            }
        }
    } // Bruteforcing : O(NM(N+M)) -> 100 * 200 이므로 가능

    for(int i =0; i<g; ++i)
        p[i] = i;
    // DSU  초기화

    while(!pq.empty()){
        ll c, a, b;
        tie(c,a,b) = pq.top();
        pq.pop();
        c *= -1;
        if(c < 2) continue;
        //cout << c <<" "<<a <<" "<<b<<"\n";
        if(u(a,b)) ans += c;
    } // MST -> Kruskal Algorithm

    for(int i =0; i<g ; ++i){
        for(int j =0; j<g; ++j){
            if(f(i) != f(j)) {
                cout << -1;
                return 0;
            }
        }
    } // 연결되지 않은 섬이 있는지 확인

    cout << ans;

    return 0;
} // MST, BFS, DSU, Bruteforcing

이번에 푼 문제처럼 여러 알고리즘들이 조화롭게 섞여있는 문제는 참 좋은 문제인 것 같습니다. 다만, 이걸 풀고나서 티어를 확인해보니 제 체감상의 난이도보다 높아서 놀랐습니다. 제가 푼 시점으로는 난이도가 G1으로 되어있기는 한데 저는 풀면서 심하면 G3~4 까지도 갈 수 있을 것 같다라는 생각했습니다. 그래도 문제가 적당한 구현 난이도도 있으면서 알고리즘들끼리 잘 섞여있어서 재밌게 풀 수 있었습니다. 오랜만에 재밌는 그래프 문제를 풀어보았습니다.

 

* 그러고보니 이번 문제 풀이부터 조건들에 존댓말을 쓰고, 주요 알고리즘들 및 시간복잡도에 대해서 볼드체로 적어볼까 합니다. 이래야 좀 더 가독성이 사는 것 같네요.