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

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제를 보면 섬의 개수도 적고 격자의 크기도 생각보다 작기 때문에 풀이 방법만 잘 생각하면 여유롭게 풀 수 있는 문제다.

 

먼저 섬과 다른 섬의 연결은 오직 직선으로 만들어진 다리로 연결되어야 하며, 이 때 다리의 길이는 2 이상이어야 한다.

 

위 조건에 맞게 섬끼리 연결되는 다리의 길이만 계산하면 Prim 알고리즘이나 크루스칼 알고리즘을 이용해 모든 섬이 연결되는데 드는 최소 비용계산할 수 있다.

 

그렇다면 어떻게 섬끼리 연결되는 다리의 길이를 계산할지 알아보자.

 

 

먼저 하나의 섬에는 같은 번호가 오도록 아래 그림과 같이 번호를 할당해 준다. 

 

이때, 섬의 번호를 할당하는 방법은 BFS나 DFS를 이용해 탐색하면서 붙어있는 상태라면 같은 섬이므로 같은 번호를 할당해 주면 된다.

 

 

탐색 알고리즘으로 섬의 번호를 정했다면, 다른 섬으로 가는 비용을 계산해야 한다.

 

계산하는 방법은 다음과 같이 계산했다.

 

1. 이중 for문으로 모든 땅을 탐색하는데, 만약 현재 땅이 섬이라면 4방향으로 다리를 만들어 다른 섬에 도달할 수 있는지 체크한다. 
2. 만약 다른 섬에 도달할 수 있을 경우 다리의 길이가 2 이상인지 체크한다. (2 미만은 다리를 만들 수 없다)
3. 만약 다리의 길이가 2 이상이라면 연결된 두 섬의 비용을 최소 비용으로 갱신한다. (A섬과 B섬의 다리를 만드는 비용을 최소화 시킨다)

 

위 방법이 어떻게 경로를 찾는지 아래 그림을 통해 쉽게 알아보자.

 

초록 동그라미를 친 부분에서 다리를 만들 수 있는지 탐색하는 경우 왼쪽, 아래는 다리를 만들 수 없다.

마찬가지로 위에는 다른 섬이 없기 때문에 다리를 만들 수 없다.

 

반면, 오른쪽 방향으로 나아가다보면 1번 섬에 도달하며, 만들 수 있는 다리의 길이가 4이기 때문에 다리를 만들 수 있다.

 

이 경우도 똑같이 위 방법을 따라서 다리를 만들면 된다.

 

오른쪽으로 3번 섬과 연결되는 길이 3의 다리를 만들 수 있고, 아래쪽으로 4번섬과 연결되는 길이 2의 다리를 만들 수 있다.  

 

이렇게 모든 섬들 간의 다리의 비용을 계산하면 Prim알고리즘과 크루스칼 알고리즘을 이용해 MST를 계산할 수 있다.

 

 

최종적으로 모든 섬은 연결할 수 있다면 비용을 출력하고, 모든 섬을 연결할 수 없다면 -1을 출력하면 된다.

 

 

 

 

 

​

[아이디어 정리]

1. 탐색 알고리즘(BFS, DFS)를 이용해 섬에 번호를 부여한다.
2. 이중 for문을 이용해 현재 땅이 섬이라면 4방향으로 다리를 만들 수 있는지 탐색하고, 비용을 저장한다.
3. 모든 섬들 간의 최소 비용이 계산되면, Prim알고리즘이나 크루스칼 알고리즘을 이용해 MST를 계산한다.
4. 만약 모든 섬을 방문할 수 있다면 MST의 비용을 출력하고, 모든 섬을 방문할 수 없다면 -1을 출력한다.

 

 

 

Code

 

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;

struct cmp {
    bool operator()(const pair<int, int>&a, const pair<int, int>&b) const
    {
        return a.second > b.second;
    }
};

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

void BFS(vector<vector<int>> &V, int y, int x, int idx) {
    queue<pair<int, int>>q;
    q.push(make_pair(y, x));
    pair<int, int> np;
    int ny, nx;
    V[y][x] = idx;
    
    while (!q.empty()) {
        np = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            ny = np.first + dy[i], nx=np.second+dx[i];
            if (0 <= ny && ny < V.size() && 0 <= nx && nx < V[0].size()&&V[ny][nx]==-1) {
                V[ny][nx] = idx;
                q.push(make_pair(ny, nx));
            }
        }
    }
}

void Calc(vector<vector<int>>& V, int y, int x, vector<vector<int>> &graph)
{
    int ny, nx;
    int cnt;
    for (int i = 0; i < 4; i++) {
        ny = y + dy[i], nx = x + dx[i];
        cnt = 0;
        while(true)
        {
            if (0 <= ny && ny < V.size() && 0 <= nx && nx < V[0].size())
            {
                if (V[ny][nx] != 0) {
                    if (cnt >= 2)
                    {
                        graph[V[y][x]][V[ny][nx]] = min(graph[V[y][x]][V[ny][nx]], cnt);
                    }
                    break;
                }
                ny += dy[i], nx += dx[i];
                cnt++;
            }
            else
            {
                break;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int N, M;
    cin >> N >> M;
    vector<vector<int>> V(N, vector<int>(M));
    int a;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> a;
            V[i][j] = -a;
        }
    }
    int idx = 1;
    for (int i = 0; i < N; i++) // 땅 생성
    {
        for (int j = 0; j < M; j++) {
            if (V[i][j] == -1)
            {
                BFS(V, i, j, idx);
                idx++;
            }
        }
    }
    
    vector<vector<int>> graph(idx, vector<int>(idx,150)); 
    for (int i = 0; i < N; i++) { // 비용계산
        for (int j = 0; j < M; j++) {
            if (V[i][j] != 0) {
                Calc(V, i, j, graph);
            }
        }
    }

    priority_queue<pair<int, int>, vector<pair<int,int>>, cmp> q; //Prim 알고리즘
    vector<bool> visited(idx, false);
    q.push({ 1,0 });
    pair<int, int> pInfo;
    int cost = 0;
    while (!q.empty()) {
        pInfo = q.top();
        q.pop();
        if (!visited[pInfo.first]) {
            visited[pInfo.first] = true;
            cost += pInfo.second;
            for (int i = 1; i < idx; i++) 
            {
                if (!visited[i]&&graph[pInfo.first][i]!=150)
                {
                    q.push(make_pair(i,graph[pInfo.first][i]));
                }
            }
        }
    }
    for (int i = 1; i < idx; i++) { // 모든 섬 연결 체크
        if (!visited[i]) {
            cout << -1;
            return 0;
        }
    }
    cout << cost;

    return 0;
}

 

---

알고리즘 자체는 매우 단순한 문제다.

단지 섬과 다른 섬의 연결을 어떻게 처리할지만 구현하면 쉽게 풀 수 있는 문제다.