[백준][C++] 17472 다리 만들기 2

 

 

알고리즘 종류

    - MST

 

 

 

사고 과정

    1. 섬에 번호를 표시합니다.

    2. 각 섬의 격자에서 연결 가능한 다리를 모두 구합니다.

        2-1. 이중 for문으로 땅에서 4방향으로 뻗어서 다른 섬에 닿으면 연결된 섬과 거리를 저장합니다.

    3, Kruskal 알고리즘을 사용합니다.

        3-1. 다리가 저장된 벡터를 거리 오름차순으로 정렬합니다.

        3-2. 하나 씩 꺼내서 최소 연결 다리를 만듭니다.

    4. 모든 섬이 연결되었는지 확인합니다.

        4-1. Union-Find 알고리즘에서 Find을 이용해서 부모가 모두 동일하면 섬이 모두 연결되었습니다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
 
using namespace std;
 
int n, m;
int mark = 1;
 
int mat[11][11];
int isVisited[11][11];
int parents[7];
 
vector<pair<pair<int, int>, int> > edges;
vector<pair<int, int> > locations;
 
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
 
bool isValid(int y, int x){
    return (y>=0 && y<n) && (x>=0 && x< m);
}
 
// 섬에 번호를 표시합니다. BFS 
void mark_island(){
    // 좌료를 저장해준 값을 가져옵니다. 
    for(int i=0; i<locations.size(); i++){
        int y = locations[i].first;
        int x = locations[i].second;
        
        if(isVisited[y][x]) continue;
        
        queue<pair<int,int> > q;
        q.push({y, x});
        mat[y][x] = mark; // 현재 위치 표시합니다. 이거 안해서 시간을 낭비했습니다. 
        
        while(!q.empty()){
            y = q.front().first;
            x = q.front().second;
            q.pop();
            
            for(int d=0; d<4; d++){
                int ny = y + dir[d][0];
                int nx = x + dir[d][1];
                // 이동하는 곳이 물, 방문했던 곳, 범위 밖이면 하지 않습니다. 
                if(mat[ny][nx] == 0) continue;
                if(isVisited[ny][nx]) continue;
                if(!isValid(ny, nx)) continue;
                
                isVisited[ny][nx] = 1;
                mat[ny][nx] = mark;
                
                q.push({ny, nx});
            }
            
        }
        // 섬 하나를 끝냈으면 다음 섬을 기약합니다. 
        mark ++;
    }
    
}
 
// 섬을 연결하는 모든 길을 찾습니다. 
void find_paths(){
    
    for(int y=0; y<n; y++){
        for(int x=0; x<m; x++){
            if(mat[y][x] == 0) continue;
            
            for(int d=0; d<4; d++){
                int ny = y + dir[d][0];
                int nx = x + dir[d][1];
                
                // 육지에서 다음으로 갈 장소가 육지거나 범위 밖이면 하지 않습니다. 
                if(mat[ny][nx]) continue;
                if(!isValid(ny, nx)) continue;
                 
                int dist = 0;
                while(true){
                    // 다리 길이를 늘려줍니다. 
                    ny += dir[d][0];
                    nx += dir[d][1];
                    dist++;
                    // 범위 밖이거나 자기 자신이면 하지 않습니다. 
                    if(!isValid(ny, nx) || mat[ny][nx] == mat[y][x]) break;
                    // 다른 섬에 도착하면 길이가 1이하인 것은 제외하고 저장합니다. 
                    if(mat[ny][nx]){
                        if(dist <= 1) break;
                        edges.push_back({{mat[y][x], mat[ny][nx]}, dist});
                        break;
                    }
                }
                
            }
            
        }
    }
    
}
 
 
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
    return a.second < b.second;
}
 
int getParent(int x){
    if(parents[x] == x) return x;
    return parents[x] = getParent(parents[x]);
}
 
void unionParents(int a, int b){
    a = getParent(a);
    b = getParent(b);
    
    if(a < b) parents[b] = a;
    else parents[a] = b;
}
 
// MST 
void kruskal(){
    // krukal을 위해서 다리 길이를 오름차순으로 정렬합니다.  
    sort(edges.begin(), edges.end(), cmp);
    
    for(int i=1; i<=mark; i++) parents[i] = i;
    
    int sum = 0;
    for(int i=0; i<edges.size(); i++){
        if(getParent(edges[i].first.first) != getParent(edges[i].first.second)){
            sum += edges[i].second;
            unionParents(edges[i].first.first, edges[i].first.second);
        }
    }
    
    // 모든 섬이 연결되었는지 확인합니다.
    // 모든 섬에서 부모를 구해서 부모가 같으면 됩니다.
    // 부모가 다르게 나오면, 모든 섬이 연결되지 않았습니다. 
    int firstIsland = getParent(1);
    for(int i=2; i<mark; i++){
        if(firstIsland != getParent(i)){
            cout << -1 << endl;
            return;
        }
    }
    
    cout << sum << endl;
}
 
 
int main(void){
    
    cin >> n >> m;
    
    // 입력을 받습니다. 
    int state;    
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> state;
            mat[i][j] = state;
            // 섬일 경우, y와 x의 좌료를 넣습니다.
            // 2중 for문을 피할려고 하는 것입니다. 2중 for문을 사용해도 
            // 시간초과는 나지 않습니다. 
            if(state) locations.push_back({i, j});
        }
    }
    
    // 섬에 번호를 표시합니다. 
    mark_island();
    // 섬을 잇는 다리를 모두 찾습니다. 
    find_paths();
    // 모든 섬을 연결하는 다리의 최소 길이를 구합니다. 
    kruskal();
}

 

 

시행착오

    - 섬에 번호를 표시하는 과정에서 첫 번째 위치를 표시하지 않은 실수를 했다. 그래서 섬의 크기가 1인 경우에서 오류가 발생했다.

 

    - 알고리즘 전체 흐름은 구체적으로 생각했지만, 섬이 모두 연결되었는지 확인하는 방법을 잊고 있었다. 처음에 섬의 개수만큼 배열을 만들어서 연결되었는지 확인하는 방법을 떠올렸지만 잘못 구현했다. 그래서 찾아보니 Union-Find에서 Find을 그대로 이용하면 쉽게 확인할 수 있었다. 두 개의 섬의 부모가 같으면 두 섬은 연결되어 있다. 

 

    - 이전에 한 번 실패하고 어렵다고 느껴서 도전하지 않고 있었다. 이렇게 다시 풀어보게 된 것은 3개월만이다. 처음에 실패했던 문제에 대한 두려움이 있었지만, 쉽게 방법을 떠올릴 수 있었다. 이전보다 더 발전된 것을 스스로 느꼈다.