취업/Algorithm.
백준 17472. 다리만들기2
Azderica
2020. 4. 10. 23:58
다리만들기2
Problem?
문제.
Solution
- bfs를 통해 각 섬에 번호를 붙인다
- 완전 탐색을 통해 다리를 만든다.
- kruskal algorithm을 통한 MST를 만든다.
- 모두 연결된 경우에 한해서 출력하고 그 외에는 -1을 출력한다.
Code
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 100
#define K_MAX 6 + 1
pair<int, int> dir[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
int N, M, label = 0;
int board[MAX][MAX];
bool visited[MAX][MAX];
int k_board[K_MAX][K_MAX];
int parent[K_MAX];
vector<pair<int, pair<int, int>>> graph;
int answer = 0;
void bfs(int y, int x, int label) {
queue<pair<int, int>> q;
q.push({ y, x });
board[y][x] = label;
visited[y][x] = true;
while (!q.empty()) {
int curY = q.front().first;
int curX = q.front().second;
q.pop();
for (int d = 0; d < 4; d++) {
int nextY = curY + dir[d].first;
int nextX = curX + dir[d].second;
if (0 <= nextY && nextY < N && 0 <= nextX && nextX < M) {
if (!visited[nextY][nextX] && board[nextY][nextX]) {
q.push({ nextY, nextX });
board[nextY][nextX] = label;
visited[nextY][nextX] = true;
}
}
}
}
}
void make_bridge(int y, int x) {
int graph_id = board[y][x];
for (int d = 0; d < 4; d++) {
int cnt = 0;
while (true) {
int nextY = y + dir[d].first * (cnt + 1);
int nextX = x + dir[d].second * (cnt + 1);
if (0 > nextY || nextY >= N || 0 > nextX || nextX >= M)
break;
else if (board[nextY][nextX] == graph_id)
break;
else if (board[nextY][nextX] == 0) {
cnt++;
continue;
}
else {
if (cnt >= 2) {
int graph_id2 = board[nextY][nextX];
if (k_board[graph_id][graph_id2]) {
k_board[graph_id][graph_id2] = min(cnt, k_board[graph_id][graph_id2]);
k_board[graph_id2][graph_id] = min(cnt, k_board[graph_id][graph_id2]);
}
else {
k_board[graph_id][graph_id2] = cnt;
k_board[graph_id2][graph_id] = cnt;
}
}
break;
}
}
}
}
int collapsingFind(int n) {
int root;
for (root = n; parent[root] >= 1; root = parent[root]);
for (int i = n; i != root; i = parent[i])
parent[i] = root;
return root;
}
void weightedUnion(int i, int j) {
int temp = parent[i] + parent[j];
if (parent[i] > parent[j]) {
parent[i] = j;
parent[j] = temp;
}
else {
parent[j] = i;
parent[i] = temp;
}
}
void kruskal() {
for (int i = 1; i <= label; i++)
for (int j = i; j <= label; j++)
if (k_board[i][j])
graph.push_back(make_pair(k_board[i][j], make_pair(i, j)));
sort(graph.begin(), graph.end());
for (int i = 1; i <= label; i++)
parent[i] = -1;
for (int i = 0; i < graph.size(); i++) {
int p = collapsingFind(graph[i].second.first);
int q = collapsingFind(graph[i].second.second);
if (p != q) {
weightedUnion(p, q);
answer += graph[i].first;
}
}
}
bool isAllConnected() {
bool flag = false;
for (int i = 1; i <= label; i++) {
if (parent[i] == -1)
return false;
if (parent[i] < -1) {
if (flag) // 제일 큰 부모는 하나만 있어야한다.
return false;
flag = true;
}
}
return true;
}
int main(int argc, const char* argv[]) {
// input
cin >> N >> M;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
scanf("%d", &board[i][j]);
// solution 1 - bfs
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (!visited[i][j] && board[i][j]) {
label++;
bfs(i, j, label);
}
// solution 2 - make bridge
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (board[i][j])
make_bridge(i, j);
// solution 3 - kruskal
kruskal();
// output
if (isAllConnected())
cout << answer << "\n";
else
cout << "-1\n";
return 0;
}
collapsingFind와 weightedUnion을 사용했다.