ksh021144

ksh021144

Learn more, Do more.

백준 17472 - 다리 만들기 2

3 분 소요

백준 17472 문제 바로가기

풀이

모든 섬을 연결하기 위해 필요한 다리 길이의 최솟값을 구해야 한다.

  1. 각 섬이 동일한 섬인지 판별하기 위해서 상하좌우로 인접한 섬끼리는 넘버링(numbering)을 수행하였고, 이 과정에서 DFS를 활용하였다. (BFS로 해도 무방하다.)

    (시작하는 섬의 번호, 도착하는 섬의 번호, 두 섬을 잇는데 필요한 다리 길이)의 정보를 Node 구조체(src, dest, len)으로 표현하였고, 각 섬을 최소 길이로 이어야 하므로 우선순위 큐 라이브러리에서 값을 꺼내올 때 len 값이 가장 작은 값부터 접근할 수 있도록 bool operator< 연산자를 오버로딩하였다.

  2. 모든 섬의 임의의 위치(값이 1인 위치)에서 바다 위치(값이 0인 위치)로 일직선으로 나아가면서 섬에 도달할 때까지 반복한다. 이때, 시작 위치의 섬 번호와 도착 위치의 섬 번호가 다르면서 다리 길이가 2이상을 만족하면 이 값을 큐에 저장한다. 이 과정은 상하좌우 4방향에 대해 반복된다.

  3. 정점의 개수가 N개(이 문제에서는 landCnt개)인 그래프에서 MST를 이루기 위한 최소 간선의 개수는 (N-1)이다. 따라서 임의의 두 섬을 연결한 결과(merge)가 true이면 pickCnt 값을 1씩 증가시키고, pickCnt 값이 섬의 개수(landCnt) - 1을 만족하면 MST가 정상적으로 형성된 것이다.

소스 코드

// since C++11
// 19 minutes
#include <iostream>
#include <queue>
using namespace std;

const int dr[] = { -1,1,0,0 };
const int dc[] = { 0,0,-1,1 };

struct Node {
    int src;
    int dest;
    int len;
    bool operator<(const Node& other) const {
        return len > other.len;
    }
};
priority_queue<Node> pq;

int N, M;
int landCnt; // land count
int field[10][10];
int ans;

int number[10][10]; // land number

// MST
int parent[7]; // max land conut : 6
void initMST() {
    for (int i = 1; i <= landCnt; ++i) {
        parent[i] = i;
    }
}
int find(int u) {
    if (parent[u] == u) {
        return u;
    }
    return parent[u] = find(parent[u]);
}
bool merge(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v)
        return false;
    parent[u] = v;
    return true;
}


inline static bool isRange(const int& r, const int& c) {
    return 0 <= r && r < N && 0 <= c && c < M;
}

void dfs(int r, int c) {
    number[r][c] = landCnt;
    for (int d = 0; d < 4; ++d) {
        int nr = r + dr[d];
        int nc = c + dc[d];
        if (!isRange(nr, nc) || field[nr][nc] == 0 || number[nr][nc] != 0) continue;
        dfs(nr, nc);
    }
}
void landNumbering() {
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < M; ++c) {
            if (field[r][c] == 1 && number[r][c] == 0) {
                ++landCnt;
                dfs(r, c);
            }
        }
    }
}

void go(int r, int c) {
    for (int d = 0; d < 4; ++d) {
        int nr = r;
        int nc = c;
        int len = 0;
        while (true) {
            nr += dr[d];
            nc += dc[d];
            if (!isRange(nr, nc)) break;

            if (field[nr][nc] == 0) { // sea
                ++len;
            }
            else { // land
                // startPoint != endPoint --> valid position
                // startPoint = number[r][c]
                // endPoint   = number[nr][nc]
                if (number[r][c] != number[nr][nc] && len >= 2) {
                    pq.push({ number[r][c], number[nr][nc], len });
                }
                break;
            }
        }
    }
}
void goBridge() {
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < M; ++c) {
            if (field[r][c] == 1) {
                go(r, c);
            }
        }
    }
}


int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    cin >> N >> M;
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < M; ++c) {
            cin >> field[r][c];
        }
    }

    landNumbering();
    goBridge();


    initMST();
    int pickCnt = 0;
    // MST condition == link count : (landCnt - 1)
    while (!pq.empty()) {
        const Node now = pq.top();
        pq.pop();
        if (merge(now.src, now.dest)) {
            ans += now.len;
            ++pickCnt;
            if (pickCnt == landCnt - 1) {
                break;
            }
        }
    }

    if (pickCnt == landCnt - 1) {
        cout << ans;
    }
    else {
        cout << -1;
    }

    return 0;
}

참고