백준 17472번 다리 만들기 2 C++ 구현, BFS, MST, 브루트포스 알고리즘

리뷰

모든 노드를 연결하는 최소비용을 구하는 문제, 노드가 섬이라는 점에서 2차원 시뮬레이션 구현 문제이다.

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

 

문제 풀이

1. n과 m값을 입력 받고 2차원 맵을 입력 받는다.
2. 각각의 섬을 노드화 시켜준다. n * m맵을 순회하며 1을 만날 경우 바다가 아닌 지형은 모두 index로 맞추어 준다, 나는 2부터 index를 매겨줬고, 이때 노드의 개수 또한 세어주고, 해당 노드의 시작 좌표를 구조체 형태로 큐에 추가해 준다.
3. 큐에 추가된 노드를 기준으로 bfs를 실행해 각 섬까지의 모든 간선을 구해 edges 벡터에 추가해 준다.
4. edges 벡터를 간선 기준으로 정렬 해주고, 유니온 파인드를 통해 최소 간선 비용을 구해준다.
5. 만약 모든 노드가 연결되지 못한다면 -1를 출력하고, 모든 노드가 연결 되었으면 최소 간선 비용을 출력해 준다.

 

참고 사항

1. chk_inner 함수 상세 내용

1. 일반적인 bfs로, 현재 위치로부터 바다가 아닌 갈 수 있는 땅이라면 매개변수로 입력받은 index로 모두 변경해 준다.
2. 더 이상 변경할 수 있는 땅이 없다면 while를 종료하고 빠져나와 준다.

2. bfs 함수 상세 내용

1. 섬 정보를 받아온 island 큐를 통해 각 섬의 시작 부분에서 부터 bfs를 시작해 준다.
2. 현재 위치부터 동서남북 방향으로 1자로 쭉 뻗어나가는 while 루프를 구현해 준다.
3. 만약 범위를 벗어 나거나 이미 방문처리가 된 땅을 밟을 경우 break 처리를 해주고 다른 방향 탐색
4. 자기 자신과 동일한 index를 만날 경우 방문 처리 해주고 큐에 해당 위치를 새로 추가 후 break 처리, 다른 방향 탐색
5. 다른 땅을 만나게 된 경우 방문 처리를 해주고 다리 길이가 2 이상일 경우 간선 추가 후 break, 다른 방향 탐색
6. 만약 바다를 만났을 경우 방문 처리를 해주고 탐색 진행

3. 유니온 파인드 함수 및 MST 구하기 상세 내용

1. bfs를 통해 수집된 간선 정보를 다리 길이를 기준으로 오름차순 정렬해 준다.
2. 모든 간선 정보를 탐색하면서 시작 노드와 종료 노드가 같은 집합에 속해있다면 continue
3. 만약 같은 집합에 속해있지 않다면, Union 처리를 해주고 sum 변수에 비용 추가 및 간선 연결 개수 cnt 1 증가

 

정답 코드

#include<iostream>
#include<queue>
#include<tuple>
#include<algorithm>

using namespace std;

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

int n, m;
int lst[10][10];
int nodes[8];

struct Pos {
    int d, x, y, index;
};

queue<Pos> island;

vector<tuple<int, int, int>> edges;

int Find(int a) {
    if (nodes[a] == a) return a;
    return nodes[a] = Find(nodes[a]);
}

void Union(int a, int b) {
    int rootA = Find(a);
    int rootB = Find(b);
    if (rootA == rootB) return;
    nodes[rootB] = rootA;
}

void chk_inner(int sx, int sy, int index) {
    queue<pair<int, int>> q;
    int v[10][10] = { 0, };
    q.push({ sx, sy });
    lst[sx][sy] = index;
    v[sx][sy] = 1;

    while (!q.empty()) {
        pair<int, int> cur = q.front(); q.pop();
        int cx = cur.first, cy = cur.second;
        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i], ny = cy + dy[i];
            if (0 <= nx && nx < n && 0 <= ny && ny < m && !v[nx][ny] && lst[nx][ny] == 1) {
                v[nx][ny] = 1;
                lst[nx][ny] = index;
                q.push({ nx, ny });
            }
        }
    }
}

void bfs(int sx, int sy, int index) {
    queue<Pos> q;
    q.push({ 0, sx, sy });
    int v[10][10] = { 0, };
    v[sx][sy] = 1;

    while (!q.empty()) {
        Pos pos = q.front(); q.pop();
        int cx = pos.x, cy = pos.y, cd = pos.d;
        for (int i = 0; i < 4; i++) {
            int nx = cx, ny = cy, nd = cd;
            while (1) {
                nx += dx[i];
                ny += dy[i];
                nd++;
                if (0 > nx || nx >= n || 0 > ny || ny >= m) break;
                if (v[nx][ny]) break;
                if (lst[nx][ny] == index) {
                    v[nx][ny] = 1;
                    q.push({ 0, nx, ny });
                    break;
                }
                else if (2 <= lst[nx][ny]) {
                    v[nx][ny] = 1;
                    if (nd > 2) edges.push_back({ nd - 1, index, lst[nx][ny] });
                    break;
                }
                else v[nx][ny] = 1;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    int node = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> lst[i][j];
        }
    }

    int index = 2;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (lst[i][j] == 1) {
                chk_inner(i, j, index);
                island.push({ 0, i, j, index });
                index++;
                node++;
            }
        }
    }

    while (!island.empty()) {
        Pos now = island.front(); island.pop();
        bfs(now.x, now.y, now.index);
    }

    sort(edges.begin(), edges.end());

    for (int i = 2; i < 2 + node; i++) {
        nodes[i] = i;
    }

    int sum = 0, cnt = 0;
    for (int i = 0; i < edges.size(); i++) {
        tuple<int, int, int> edge = edges[i];
        int dist = get<0>(edge), cur_n = get<1>(edge), next_n = get<2>(edge);
        if (Find(cur_n) == Find(next_n)) continue;
        Union(cur_n, next_n);
        sum += dist;
        cnt++;
    }
    if (cnt == node - 1) cout << sum;
    else cout << -1;
}