17472번 다리 만들기 2

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

1. DFS로 각 섬을 Group화 한다.(1, 2, 3, ...)

2. BFS로 각 정점끼리의 거리를 구하는데 이 때, 4가지 방향(동서남북)에 대한 배열(코드의 vertex)을

활용해야 한다. 이유는 아래 예제를 생각해보자.

(주의 : 나의 코드에서는 방문 처리를 말하는 것이 아니다. 

다른 방법으로 방문 처리를 4가지 방향으로 해도 된다. 단순 이 글에서의 설명이다.)

5 10
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 1 0 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 

3. MST로 활용하기 위해, mst vector에 {간선의 가중치, 현재 정점, 다음 정점}을 담는다.

4. 간선의 가중치를 기준으로 오름차순한다.

5. 사이클 방지를 위해 Union-Find를 활용한다.

6. MST 특성상 최소 다리 개수는 전체 정점 개수 - 1이 되어야 한다.

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 11
#define INF 987654321
 
// bfs를 위한 구조체
typedef struct info
{
    int y, x, d;
}info;
 
// mst를 위한 구조체
typedef struct info2
{
    int w, here, next;
}info2;
 
int m[Max][Max], N, M, answer, gc = 1, parent[Max], vertex[Max][4];
int dy[4] = { 0, 1, 0, -1 };
int dx[4] = { 1, 0, -1, 0 };
vector<pair<int, int> > v[Max];
vector<info2> mst;
bool visit[Max][Max];
 
bool cmp(const info2 & a, const info2 & b)
{
    if (a.w < b.w) return true;
    return false;
}
 
// 그룹화
void dfs(int r, int c, int group)
{
    visit[r][c] = true;
    m[r][c] = group;
    for (int i = 0; i < 4; i++)
    {
        int y = r + dy[i];
        int x = c + dx[i];
        if (y < 0 || y >= N || x < 0 || x >= M || visit[y][x] || !m[y][x]) continue;
        dfs(y, x, group);
    }
}
 
// 각 정점끼리의 거리 구하기. 이 때, vertex 배열을 유심히 보자.
int bfs(int sy, int sx, int from, int to)
{
    memset(visit, false, sizeof(visit));
    memset(vertex, 0, sizeof(vertex));
    visit[sy][sx] = true;
    
    queue<info> q;
    for (int i = 0; i < 4; i++) q.push({ sy, sx, i }); // 시작부터 4가지 방향을 고려해야한다.
 
    int ret = -1;
 
    while (!q.empty())
    {
        int qs = q.size();
 
        while (qs--)
        {
            int r = q.front().y;
            int c = q.front().x;
            int d = q.front().d;
 
            q.pop();
 
            // to 정점에 도착했고, 아직 그 to정점에 대한 방향(d)의 값이 설정되지 않았다면(도착하지 않았다면)
            if (m[r][c] == to) if(!vertex[to][d]) vertex[to][d] = ret;
                        
            int y = r + dy[d];
            int x = c + dx[d];
 
            if (y < 0 || y >= N || x < 0 || x >= M || visit[y][x]) continue;
 
            if (m[y][x] == 0 || m[y][x] == to) // 실수 주의
            {
                visit[y][x] = true;
                q.push({ y, x, d });
            }
        }
 
        ++ret;
    }
 
    for (int i = 0; i < 4; i++)
        if (vertex[to][i] >= 2) // 문제 조건
            return vertex[to][i];
    
    return INF;
}
 
int Find(int x)
{
    if (parent[x] == x) return x;
    return parent[x] = Find(parent[x]);
}
 
void Union(int a, int b)
{
    a = Find(a);
    b = Find(b);
 
    if (a < b) parent[b] = a;
    else parent[a] = b;
}
 
int main(void)
{
    //cin.tie(0);
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++)     scanf("%d", &m[i][j]);
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)    
            if (!visit[i][j] && m[i][j])
            {
                dfs(i, j, gc);
                ++gc;
            }
 
    --gc;
 
    for (int i = 1; i <= gc; i++) parent[i] = i;
 
    // v[정점] = {해당 정점의 좌표들}
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (m[i][j])
                v[m[i][j]].push_back({ i, j });    
 
    for (int i = 1; i <= gc; i++)
    {
        for (int j = i + 1; j <= gc; j++)
        {        
            int Min = INF; // 최솟값
            bool calc = false;
 
            for (auto pos : v[i])
            {
                int get = bfs(pos.first, pos.second, i, j);
 
                if (get >= 2 && get != INF)
                {
                    calc = true;
                    Min = min(Min, get);
                }
            }
 
            if (calc) mst.push_back({ Min, i, j });        
        }
    }
 
    // 간선의 가중치를 중심으로 오름차순(MST를 활용하기 위해)
    sort(mst.begin(), mst.end(), cmp);
 
    int cnt = 0;
 
    for (auto i : mst)
        if (Find(i.here) != Find(i.next))
        {
            Union(i.here, i.next);
            answer += i.w;
            ++cnt;
            if (cnt == gc - 1) break;
        }
    
    // MST 특성상 간선의 개수는 전체 정점 - 1이 되어야 한다.
    printf("%d\n", cnt == gc - 1 ? answer : -1);
 
    return 0;
}