[BOJ알고리즘, C++]#17472_다리 만들기 2, DFS, 최소 신장 트리(MST), 크루스칼(Kruskal)

 

#1. 문제

 

17472번: 다리 만들기 2

 

---

 

#2. 풀이

 

1. 그래프

 

[자료구조]#6_그래프

 

그래프 자료구조는 노드와 간선의 집합으로 이루어진 비 선형 자료구조입니다. 그래프 자료구조의 노드 간 연결 관계를 간선으로 표현하며, 간선의 방향성, 연결 강도 등으로 다양한 형태의 그래프 자료구조를 표현할 수 있습니다.

 

2. DFS(깊이 우선 탐색)

 

[자료구조]#6_그래프

 

깊이 우선 탐색은 그래프의 모든 정점을 탐색하는 방법 중 하나로, 출발 정점으로부터 더 이상 확장 불가능한 단말까지 깊이 우선적으로 탐색을 진행하는 알고리즘입니다. 일반적으로, DFS는 재귀 호출 혹은 스택 자료구조를 활용하여 구현 가능합니다.

 

3. 최소 신장 트리

 

[자료구조]#6_그래프

 

신장 트리란, 그래프 내 모든 정점을 최소한의 간선으로 순환 구조 없이 연결하는 부분 그래프를 의미합니다. 따라서, 최소 신장 트리는 가중치 그래프에서 간선들이 갖는 가중치의 합이 최소가 되는 신장 트리를 의미합니다. 대표적인 최소 신장 트리 알고리즘은 크루스칼, 프림, 그리고 솔린 알고리즘이 있습니다.

 

4. 크루스칼 알고리즘

 

[자료구조]#6_그래프

 

크루스칼 알고리즘은 간선 중심의 최소 신장 트리 알고리즘입니다. 크루스칼 알고리즘은 먼저, 간선들을 가중치 기준 오름차순으로 정렬하고, 차례대로 Union-Find 연산을 수행하며 최소 신장 트리를 구성하는 알고리즘입니다.

 

5. DFS1-영역 찾기 유형 -> 다리 찾기 -> 크루스칼

 

1. 먼저, 영역 찾기 유형 문제에서 자주 활용한 DFS를 통해 각 섬을 구분해 줍니다.
2. 그리고, 각 섬을 구성하는 정점들로부터 네 방향으로 다리 연결을 가정하고, 다리 연결이 가능할 경우 별도의 간선 목록에 해당 간선을 추가해 줍니다. 이때, 간선은 구조체 형식으로 출발점, 도착점, 그리고 길이를 데이터 필드로 갖도록 합니다.
3. 마지막으로, 위에서 찾은 다리 목록들에 대하여 크루스칼 알고리즘을 수행하고, 결과를 출력합니다!

 

---

 

#3. 코드

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define MAX 10
using namespace std;

int N, M;
int map[MAX][MAX];
bool visited[MAX][MAX];
vector<pair<int, pair<int, int>>> edges;
int parent[MAX * MAX];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void dfs(int x, int y, int id)
{
    visited[x][y] = true;
    map[x][y] = id;
    for (int dir = 0; dir < 4; ++dir)
    {
        int nx = x + dx[dir], ny = y + dy[dir];
        if (nx >= 0 && nx < N && ny >= 0 && ny < M && map[nx][ny] == 1 && !visited[nx][ny])
        {
            dfs(nx, ny, id);
        }
    }
}

void findBridges(int id)
{
    for (int x = 0; x < N; ++x)
    {
        for (int y = 0; y < M; ++y)
        {
            if (map[x][y] == id)
            {
                for (int dir = 0; dir < 4; ++dir)
                {
                    int len = 0;
                    int nx = x + dx[dir], ny = y + dy[dir];
                    while (nx >= 0 && nx < N && ny >= 0 && ny < M)
                    {
                        if (map[nx][ny] == id)
                            break;
                        if (map[nx][ny] > 0)
                        {
                            if (len >= 2)
                            {
                                edges.push_back({len, {id, map[nx][ny]}});
                            }
                            break;
                        }
                        nx += dx[dir];
                        ny += dy[dir];
                        len++;
                    }
                }
            }
        }
    }
}

int find(int x)
{
    if (x != parent[x])
        parent[x] = find(parent[x]);
    return parent[x];
}

bool unionFind(int a, int b)
{
    a = find(a), b = find(b);
    if (a == b)
        return false;
    parent[a] = b;
    return true;
}

int main()
{
    cin >> N >> M;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            cin >> map[i][j];

    int id = 1;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (map[i][j] == 1 && !visited[i][j])
            {
                dfs(i, j, id++);
            }
        }
    }

    for (int i = 1; i < id; ++i)
    {
        findBridges(i);
    }

    sort(edges.begin(), edges.end());
    for (int i = 1; i < id; ++i)
        parent[i] = i;

    // * 정답 도출을 위해, 각 섬 간의 다리 연결의 가능성 여부를 체크하는 코드에서 에러가 발생.
    int ans = 0;
    int selectedEdges = 0;

    for (auto &e : edges)
    {
        int cost = e.first, a = e.second.first, b = e.second.second;
        if (unionFind(a, b))
        {
            ans += cost;
            selectedEdges++;
            if (selectedEdges == id - 2)
                break;
        }
    }

    if (selectedEdges != id - 2)
    {
        cout << -1 << '\n';
    }
    else
    {
        cout << ans << '\n';
    }

    return 0;
}

 

---