17472 다리 만들기 2

굉장히 복합적인 시뮬레이션 문제이다. 다양한 알고리즘을 연습하기에 좋다.

문제 링크

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

풀이

우선 각각의 섬을 구분할 수 있어야 하므로 섬에 번호를 붙여주어야 한다.
반복문을 돌면서 만약 방문하지 않은 섬을 만나면 bfs를 통해 각 섬의 숫자를 +num 해주도록 하고, num번째 섬의 정보를 벡터 배열에 저장한다.
그 후 섬과 섬 사이의 거리, 즉 cost를 나타내는 2차원 dis 배열을 초기화한다. 초기화 하는 값은 임의의 큰 수 101로 하였다. 후에 섬을 연결하는 cost 값으로 모든 섬이 연결되었는지 그렇지 않은지 판별할 것이기 때문에 충분히 큰 값으로 초기화해야 한다.
그 후 섬에서 섬까지의 길이를 구하기 위해 현재 섬에서 상하좌우로 이동하여 갈 수 있는 섬을 탐색하기 위해 dfs를 돌린다.
현재 섬에서 한 방향으로 쭉 나아가면 만날 수 있는 섬을 탐색하고,
만약 그런 섬이 존재한다면 그 섬까지의 cost를 확인하고 그 cost가 기존의 cost보다 작다면 dis 배열을 업데이트 해준다.
만약 좌표를 벗어나거나 cost가 2보다 작다면 그냥 return해야 한다.
섬과 섬 사이의 cost를 모두 구했다면 이제 크루스칼 알고리즘을 통해 최단 거리를 구할 것이다.
섬과 섬 사이의 edge 정보를 담을 Edge클래스를 선언하고, union-find를 적용시키기 위해 getParent, unionParent, find 함수를 구현해준다.
Edge들의 정보를 담을 Edge 배열 v를 선언하고,
반복문을 돌면서 노드와 cost값을 저장한다.
이 때 cost는 dis 배열에 담긴 값이다.
값을 저장한 후 sort로 cost가 오름차순이 되도록 정렬한다.
그 후 크루스칼 알고리즘을 적용시켜 가장 작은 cost를 가진 edge부터 연결시켜준다.
만약 비용의 합 ans가 101보다 크거나 같다면, 연결되지 않은 섬과 섬이 존재했다는 것이므로(연결됐다면 dfs를 돌 때 101보다 훨씬 작은 수로 갱신되었을 테니까) -1을 출력한다.
그렇지 않은 경우 ans를 출력하면 된다.

C++ 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define endl '\n'

using namespace std;

int arr[10][10];
bool visit[10][10];
int root[6];
int N, M;
vector<pair<int,int>> land[6];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
int dis[6][6];

int getParent(int x){
    if(root[x] == x) return x;
    return root[x] = getParent(root[x]);
}

void unionParent(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a < b) root[b] = a;
    else root[a] = b;
}

bool find(int a, int b){
    a = getParent(a);
    b = getParent(b);
    if(a == b) return true;
    return false;
}

// 섬을 노드로 섬사이의 거리를 edge로
class Edge{
public:
    int node[2];
    int cost;
    Edge(int a, int b, int cost){
        this->node[0] = a;
        this->node[1] = b;
        this->cost = cost;
    }
    bool operator <(Edge &edge){
        return this->cost < edge.cost;
    }
};

void bfs(int i, int j, int num){
    queue<pair<int,int>> q;
    q.push({i,j});
    visit[i][j] == true;
    arr[i][j] += num;
    while(!q.empty()){
        pair<int,int> now = q.front();
        q.pop();
        for(int i=0; i<4; i++){
            int nx = now.first+dx[i], ny = now.second+dy[i];
            if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
            if(!visit[nx][ny] && arr[nx][ny] == 1){
                visit[nx][ny] = true;
                arr[nx][ny] += num;
                land[num].push_back({nx,ny});
                q.push({nx,ny});
            }
        }
    }
}

void dfs(pair<int, int> now, int n, int start, int cost){
    // n 탐색할 방향 des 목적지 섬
    int nx = now.first + dx[n];
    int ny = now.second + dy[n];
    if(nx<0 || nx>=N || ny<0 || ny>=M) return;
    if(arr[nx][ny] != 0){
        if(arr[nx][ny] == start || cost < 2) return;
        if(dis[start-1][arr[nx][ny]-1]>cost){
            dis[start-1][arr[nx][ny]-1] = cost;
            dis[arr[nx][ny]-1][start-1] = cost;
        }
        return;
    }
    else
    	dfs(make_pair(nx, ny), n, start, cost+1);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin>>N>>M;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            cin>>arr[i][j];
        }
    }
    // 섬에 번호 붙여줌
    int num = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(arr[i][j] == 1 && !visit[i][j]){
                land[num].push_back({i,j});
                bfs(i, j, num);
                num++;
            }
        }
    }
    // dis 초기화
    for(int i=0; i<num; i++){
        for(int j=0; j<num; j++){
            dis[i][j] = 101;
        }
    }
    // 섬에서 섬끼리 길이 구함
    for(int i=0; i<num; i++){
        for(int j=0; j<land[i].size(); j++){
            // 자기 자신보다 번호가 작은 섬까지의 최적 거리는 이미 구해져있음
            for(int des=i+1; des<num; des++){
                for(int n=0; n<4; n++){
                    dfs(land[i][j], n, i+1, 0);
                }
            }
        }
    }
    // root 초기화
    for(int i=0; i<num; i++){
        root[i] = i;
    }
    vector<Edge> v; // 노드 정보 저장
    // Edge 정보 저장
    for(int i=0; i<num; i++){
        for(int j=i+1; j<num; j++){
            v.push_back(Edge(i,j,dis[i][j]));
        }
    }
    sort(v.begin(), v.end());
    int ans = 0;
    for(int i=0; i<num; i++){
        if(!find(v[i].node[0], v[i].node[1])){
            ans += v[i].cost;
            unionParent(v[i].node[0], v[i].node[1]);
        }
    }
    if(ans >= 101)
        cout<<-1<<endl;
    else
        cout<<ans<<endl;
    
    return 0;
}