[백준] 17472. 다리 만들기 2

문제 설명

나라는 섬들로 이루어지고, 모든 섬을 다리로 연결하려고 한다.
N×M 크기의 지도에서 1은 땅 0은 바다를 나타내며 섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말한다.
섬과 섬간의 다리는 직선인 경우(가로, 세로)에만 성립하며 다리의 길이가 2이상 되어야한다.

모든 섬을 연결하는 다리 길이의 최솟값을 출력하며 모든 섬을 연결하는 것이 불가능한 경우에는 -1을 출력하도록 한다.

Solution

MST를 구하는 문제이다.
다른 일반적인 MST 문제는 정점의 번호와 간선 및 비용이 친절하게 주어지나, 이 문제는 지도를 통해 정점, 간선 및 비용을 직접 구해야한다.

BFS(또는 DFS)와 크루스칼을 조합하여 문제를 해결하는 방식이다보니 재미있게 풀었다.

수행단계

섬들을 만든다
1. BFS또는 DFS를 통해 섬들을 탐색한다.
2. 각 섬들에 인덱스를 매긴다.
각 섬들을 잇는 모든 다리들을 구한다.
1. 각 섬들을 구성하는 좌표마다 가로, 세로 탐색을 수행한다.
2. 탐색 시 바다라면 카운트 값을 증가시킨다.
3. 탐색 시 땅이라면 인덱스 값을 확인한다.
  탐색이 시작된 땅의 인덱스값과 현재 도달한 땅의 인덱스 값이 다르면 카운트 값이 2이상인지 조회한다.
  카운트 값이 2이상이라면 간선 리스트에 시작 인덱스, 종료 인덱스, 카운트 값을 하나의 간선 정보로 하여 포함시킨다.
최소신장트리를 구한다.
1. 간선 리스트에 포함된 간선들의 비용을 기준으로하여 정렬한다.
2. Union-find를 사용하여 MST를 구성하며 find가 수행될때마다 간선의 비용을 누적시키고 MST에 포함되는 노드 갯수를 1씩 증가시킨다.
MST에 포함된 노드갯수와 섬들의 갯수 일치여부를 검사한다.
1. 갯수가 일치하면 누적된 간선 비용 값을 출력한다.
2. 갯수가 불일치시 -1을 출력한다.

Code

원본 배열(지도)에 정점의 인덱스 값을 할당해도 되겠지만, 본인은 unordered_map을 사용하여 해싱하는 방식으로 풀었다.
문제를 해결하는 것 외에도 본인만의 코딩컨벤션을 정립해서 읽기 쉬운 코드가 될 수 있도록 노력을 기울여야겠다.

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>

#define LAND 1
#define LEN 11
#define MAX 7

using namespace std;

int country[LEN][LEN];
bool visit[LEN][LEN];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

unordered_map<int, int> vertex_index;
int sz = 1;
vector<vector<int>> edge; //from ,to, cost

int root[MAX];
int depth[MAX]; //union by rank

int hash_func(int y, int x){
    return y*10 + x;
}

void get_vertex(int m, int n){ // y, x
    queue<pair<int,int>> q;

    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            if(country[i][j] == LAND && !visit[i][j]){
                q.push({i,j}); //y,x
                visit[i][j] = true;

                while(!q.empty()){
                    pair<int,int> tmp = q.front();

                    for(int k=0; k<4; k++){
                        int y = tmp.first + dy[k];
                        int x = tmp.second + dx[k];

                        if(1 <= x && x <= n && 1 <= y && y<= m){
                            if(country[y][x] == LAND && !visit[y][x]){
                                q.push({y, x});
                                visit[y][x] = true;
                            }
                        }
                    }

                    q.pop();
                    vertex_index[hash_func(tmp.first,tmp.second)] = sz;
                }

                sz++;
            }
        }
    }
    sz--;
}

void find_edge(int y, int x, bool flag){
    for(int i=1; i<=y; i++){
        int from = 0, to = 0, cost = 0;

        for(int j=1; j<=x; j++){
            int node = flag ? country[i][j] : country[j][i];
            if(node == LAND){
                int tmp = flag ? vertex_index[hash_func(i,j)] : vertex_index[hash_func(j,i)];

                if(from == 0){
                    from = tmp;
                }
                else{
                    to = tmp;

                    if(from != to){ //to를 만난 경우
                        if(cost >= 2){
                            edge.push_back({from, to, cost});
                        }
                        cost = 0;
                        from = to;
                        to = 0;
                    }
                    else cost = 0;
                }
            }
            else if(from != 0) cost++;
        }
    }
}

void get_edge(int m, int n){
    find_edge(m, n, true); //horizontal
    find_edge(n, m, false); //vertical
}

bool cmp(vector<int> &t, vector<int> &u){
    return t[2] < u[2]; //cost 기준
}

void init(int n){
    for(int i=1; i<=n; i++){
        root[i] = i;
        depth[i] = 0;
    }
}

int find(int node){
    if(root[node] == node){
        return node;
    }
    else{
        return root[node] = find(root[node]);
    }
}

bool do_union(int x, int y){
    x = find(x);
    y = find(y);

    if(x==y) return false;

    if(depth[x] < depth[y]){
        root[x] = y;
    }
    else{
        root[y] = x;

        if(depth[x] == depth[y]){
            depth[x]++;
        }
    }
    
    return true;
}

int main() {
    int m, n, cnt = 0, answer = 0;
    cin >> m >> n;

    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            cin >> country[i][j];
        }
    }

    get_vertex(m, n);
    get_edge(m, n);
    sort(edge.begin(), edge.end(), cmp);

    init(MAX - 1);

    for(vector<int> e : edge){
        if(do_union(e[0], e[1])){
            answer += e[2];
            cnt++;
        }

        if(cnt == sz-1) break;
    }

    if(sz < 2 || cnt != sz - 1) answer = -1;

    cout << answer;
}

문제 설명

Solution

수행단계

Code

CATALOG