[C/C++] 백준 17472 - 다리 만들기 2

[C/C++] 백준 17472 - 다리 만들기 2

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

문제를 읽어보면 다리는 항상 일직선이며 다리가 중복되더라도 길이는 각각 증가해야하고 모든 섬을 잇는 최소 거리를 구하고 싶다고 했다.

각 섬을 노드, 다리를 에지라고 생각해보면 모든 노드를 최소거리로 잇는 거리를 찾고 싶다는 얘기가 되고 최소 스패닝 트리 문제라는 것을 확인 할 수 있다.

최소 스패닝 트리면 크루스칼 알고리즘을 사용하면 쉽게 구현이 가능하지만 노드와 다리를 어떻게 찾아서 값을 집어넣을지가 관건이다.

이 문제를 해결하기 위해 내가 쓴 구현 방법은 다음과 같다.

1. 각 노드를 인식해야하므로 1로 체크된 부분만 bfs를 돌면서 서로 다른 노드 숫자를 부여해준다

(백준 - 단지번호 붙이기 문제 참고)

2. 노드를 잇는 에지를 찾기 위해서 for문으로 모든 좌표들을 검사해서 다리가 이어지는지 아닌지 확인해서 이어질 경우, 그 길이만큼을 edge 길이로 취급해서 저장한다.

3. 그래프 정보가 전부 입력되면 크루스칼 알고리즘 사용 후 노드들의 root를 확인해서 혹시라도 이어지지 않은 노드가 있는지 확인한다.

<소스 코드>

#include #include #include #include #include using namespace std; int n,m, ans; int arr[11][11]; bool visit[11][11]; int dx[4] = { -1,1,0,0 }; int dy[4] = { 0,0,-1,1 }; int cycle[7]; int num; vector >> v; // 앞은 연결된 노드 번호 뒤는 간선 가중치 queue >q; int find(int i) { if (i == cycle[i]) return i; return cycle[i] = find(cycle[i]); } void union_set(int a, int b) { int root1 = find(a), root2 = find(b); if (root1 == root2) return; cycle[root2] = root1; return; } void numbering(int c) { int x , y; while (!q.empty()) { x = q.front().first; y = q.front().second; visit[x][y] = true; arr[x][y] = c; for (int i = 0; i < 4; i++) { if ((x + dx[i] >= 0 && x + dx[i] < n) && (y + dy[i] >= 0 && y + dy[i] < m)) { if (visit[x + dx[i]][y + dy[i]] == false && arr[x + dx[i]][y + dy[i]] == -1) q.push(make_pair(x + dx[i], y + dy[i])); } } q.pop(); } num++; return; } void run() { int cnt = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (arr[i][j] < 0) { q.push(make_pair(i, j)); cnt++; numbering(cnt); } } } return; } void findEdge1() // 가로로 지나는 다리 찾아서 간선으로 만들기 { int s, d; bool flag; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (arr[i][j] > 0) { flag = false; s = j; int cnt = 0; for (int k = j + 1; k < m; k++) { if (arr[i][k] == 0) cnt++; else { d = k; flag = true; break; } } if (cnt >= 2 && flag) { if (arr[i][s] != arr[i][d]) v.push_back(make_pair(cnt, make_pair(arr[i][s], arr[i][d]))); } } } } return; } void findEdge2() // 세로로 지나는 다리 찾아서 간선으로 만들기 { int s, d; bool flag; for (int j = 0; j < m; j++) { for (int i = 0; i < n; i++) { if (arr[i][j] > 0) { flag = false; s = i; int cnt = 0; for (int k = i + 1; k < n; k++) { if (arr[k][j] == 0) cnt++; else { d = k; flag = true; break; } } if (cnt >= 2 && flag) { if(arr[s][j]!= arr[d][j]) v.push_back(make_pair(cnt, make_pair(arr[s][j], arr[d][j]))); } } } } return; } int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; int t; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> t; if (t == 1) t *= -1; arr[i][j] = t; } } for (int i = 0; i <= 6; i++) cycle[i] = i; run(); findEdge1(); findEdge2(); sort(v.begin(), v.end()); int w, x, y; for (int i = 0; i < v.size(); i++) { w = v[i].first; x = v[i].second.first; y = v[i].second.second; if (find(x) == find(y)) continue; else { union_set(x, y); ans += w; } } // 모든 점이 연결되지 않는 경우 -1 출력 for (int i = 1; i <= num; i++) // path compression으로 루트 갱신하기 위해서 find(i); int temp = cycle[1]; for (int i = 1; i <= num; i++) { if (temp != cycle[i]) { cout << -1 << "

"; return 0; } //cout << cycle[i] << endl; } cout << ans << "

"; return 0; /* 반례 10 6 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 */ }

구현 시 주의할 점은 모든 점이 연결되었는지 확인하는 작업을 할때 루트가 제대로 갱신되지 않은 경우가 있을 수 있으므로 반드시 find를 통해서 각 노드의 루트를 한번씩 갱신해주고 비교를 하도록 하자.

from http://lts96.tistory.com/16 by ccl(A) rewrite - 2021-10-31 18:59:55