[백준]BOJ #17472: 다리 만들기 2

작성일 | In

문제 출처: https://www.acmicpc.net/problem/17472

문제 분석

결국은 그래프로 모델링한 뒤 MST를 구하는 문제지만 그 과정이 귀찮다

풀이

img

우선 주어진 지도를 그림처럼 섬마다 숫자를 매겨주어야한다.

  1. BFS로 탐색하며 번호를 매긴 후

섬 사이에 이어질 수 있는 모든 다리를 탐색

  1. 결국 다리는 수평 혹은 수직 방향만 가능하므로 row, col을 따라 탐색
    • 다리가 여러 개 이어질 수 있으므로 최솟값만 저장

이후는 일반적인 그래프에서 MST 탐색과 동일

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
class DisjointSet {
    public:
    unordered_map<int, int> parent;

    DisjointSet(int x){
        foi(x) makeSet(i);
    }
    void makeSet(int x){
        parent[x]=x;
    }
    int Find(int tar){
        if(parent[tar]==tar) return tar;
        return parent[tar]=Find(parent[tar]);
    }
    int Union(int m, int n){
        if(parent[m]==0) makeSet(m);
        if(parent[n]==0) makeSet(n);
        int pm=Find(m); 
        int pn=Find(n);
        if(pm==pn) return 1;
        else{
            parent[pn]=pm;
            return 0;
        }
    }
};

int N, M;
int adjMat[7][7];
int board[11][11], visited[11][11];
const int dx[4]={1, -1, 0, 0};
const int dy[4]={0, 0, 1, -1};
int vertexNum=1;

int kruskal(vector<pii> &selected){
    DisjointSet sets(6);
    int ret=0;
    selected.clear();
    int u, v;
    int cost;
    // <weight,v1,v2>
    vector<pair<int, pii>> edges;
    for(u=1;u<=vertexNum-1;u++)
        for(v=1;v<=vertexNum-1;v++){
            if(adjMat[u][v]!=INF) edges.push_back({adjMat[u][v], {u, v}});
        }

    // sort by weight
    sort(edges.begin(), edges.end());

    for(auto p:edges){
        cost=p.first;
        u=p.second.first;
        v=p.second.second;
        if(sets.Find(u)==sets.Find(v)) continue;
        sets.Union(u, v);
        selected.push_back({u, v});
        ret+=cost;
    }  

    // check if all vertices are connected
    int cmp=sets.Find(1);
    for(int i=2;i<vertexNum;i++) if(sets.Find(i)!=cmp) ret=0;
    
    return ret;
}
void init(){
    cin>>N>>M;
    foi(N) foj(M) cin>>board[i][j];
}
bool inBoard(int i, int j){
    if(i>0&&i<=N&&j>0&&j<=M) return true;
    else return false;
}
void setNumBFS(int i, int j, int num){
    if(board[i][j]==0) return;
    queue<pii> q;
    q.push({i, j});
    visited[i][j]=1;
    while(!q.empty()){
        int cx=q.front().first, cy=q.front().second;
        board[cx][cy]=num;
        q.pop();
        for(int k=0;k<4;k++){
            int tx=cx+dx[k], ty=cy+dy[k];
            if(inBoard(tx, ty)&&board[tx][ty]==1&&!visited[tx][ty]){
                visited[tx][ty]=1;
                q.push({tx, ty});
            }
        }
    }
}
void setVerticesNum(){
    memset(visited, 0, sizeof(visited));
    foi(N)
        foj(M)
            if(!visited[i][j] && board[i][j]!=0)
                setNumBFS(i, j, vertexNum++);
        
}
void setAdj(){
    foi(6) foj(6) adjMat[i][j]=INF;
    int prev, next;
    int bridge_len=0;
    // horizontal
    foi(N){
        bridge_len=0;
        prev=board[i][1];
        for(int j=2;j<=M;j++){
            next=board[i][j];
            if(prev==0) prev=board[i][j];
            else if(prev!=0 && next==0) bridge_len++;
            else if(prev!=next){    // prev!=0 && next!=0 && prev!=next
                if(bridge_len<2){
                    prev=board[i][j];
                    bridge_len=0;
                }
                else{
                    adjMat[prev][next]=min(adjMat[prev][next], bridge_len);
                    adjMat[next][prev]=min(adjMat[next][prev], bridge_len);
                    prev=board[i][j];
                    bridge_len=0;
                }
            }
            else bridge_len=0;  // prev!=0 && next!=0 && prev==next
        }
    }
    
    // vertical
    foj(M){
        bridge_len=0;
        prev=board[1][j];
        for(int i=2;i<=N;i++){
            next=board[i][j];
            if(prev==0) prev=board[i][j];
            else if(prev!=0 && next==0) bridge_len++;
            else if(prev!=next){    // prev!=0 && next!=0 && prev!=next
                if(bridge_len<2){
                    prev=board[i][j];
                    bridge_len=0;
                }
                else{
                    adjMat[prev][next]=min(adjMat[prev][next], bridge_len);
                    adjMat[next][prev]=min(adjMat[next][prev], bridge_len);
                    prev=board[i][j];
                    bridge_len=0;
                }
            }
            else bridge_len=0;  // prev!=0 && next!=0 && prev==next
        }        
    }
}
void solve(){
    setVerticesNum();
    setAdj();
    vector<pii> v;
    int res=kruskal(v);
    if(res==0) cout<<"-1";
    else cout<<res;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    init();
    solve();
}

Reference