[DFS 단순 반복, BFS 반복, 크루스칼] 백준 17472 다리 만들기2 C++

 

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

#include <iostream>
#include <queue>
#include <limits.h>

using namespace std;

struct pos {
    int x, y, size, dir;
};

int n, m, ans;
int board[12][12];
int visited[12][12];
int graph[12][12];
int parent[7];
int check[7];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
vector<vector<int>> v;
queue<pos> q[7];

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

void unions(int x, int y) {
    x = getRoot(x);
    y = getRoot(y);
    if (x < y) parent[y] = x;
    else if (x > y) parent[x] = y;
}

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

void bfs(int total) {
    while (!q[total].empty()) {
        int dir = q[total].front().dir;
        int newX = q[total].front().x + dx[dir];
        int newY = q[total].front().y + dy[dir];
        int size = q[total].front().size;
         
        q[total].pop();
        if ((newX == 0) || (newY == 0) || (newX > m) || (newY > n)) continue;
        if (board[newY][newX]) {
            if (board[newY][newX] == total) continue;
            if (size < 2) continue;;
            if (graph[total][board[newY][newX]] > size) {
                graph[total][board[newY][newX]] = size;
                graph[board[newY][newX]][total] = size;
            }
        }
        else q[total].push({ newX, newY, size + 1, dir });
    }
}

void dfs(int x, int y, int total) {
    board[y][x] = total;
    visited[y][x] = 1;

    for (int i = 0; i < 4; i++) {
        int newX = x + dx[i];
        int newY = y + dy[i];
        if ((newX == 0) || (newY == 0) || (newX > m) || (newY > n)) continue;
        if (visited[newY][newX]) continue;
        if (board[newY][newX]) dfs(newX, newY, total);
        else {
            q[total].push({ x, y, 0, i }); // bfs에서 사용할 큐 저장
        }
    }
}

bool cmp(vector<int> a, vector<int> b) {
    return a[2] < b[2];
}

int main()
{
    cin >> n >> m;
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> board[i][j];
        }
    }

    int total = 0;
    memset(visited, 0, sizeof(visited));
    fill(&graph[0][0], &graph[11][12], 20);
    
    for (int i = 1; i <= 6; i++) parent[i] = i;

    // dfs로 섬마다 번호 부여 및 큐 저장(dfs 밖에 for문 필요)
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (visited[i][j]) continue;
            if (board[i][j]) {
                total++;
                dfs(j, i, total);
            }
        }
    }

    // bfs로 최단 거리 찾기
    for (int i = 1; i <= total; i++) {
        bfs(i);
    }

    // 간선 저장
    for (int i = 1; i <= total; i++) {
        for (int j = 1; j <= i; j++) {
            if (graph[i][j] != 20) {
                v.push_back({ i, j, graph[i][j] });
            }
        }
    }

    // 간선 비용 오름차순 정렬
    sort(v.begin(), v.end(), cmp);

    // 크루스칼 알고리즘
    for (int i = 0; i < v.size(); i++) {
        if (!find(v[i][0], v[i][1])) {
            unions(v[i][0], v[i][1]);
            ans += v[i][2];
        }
    }

    // 연결하지 못한 정점 존재 여부
    for (int i = 1; i <= total; i++) {
        if (getRoot(i) != 1) {
            cout << -1; 
            return 0;
        }
    }

    cout << ans;
    
    return 0;
}