https://www.acmicpc.net/problem/17472
[필자 사고]
많은 알고리즘을 사용하여 풀어야 되는 문제이다.
필자는 unionFind() 알고리즘/ 최소 스패닝 트리 알고리즘을 적용하여 문제를 해결해 나갔다.
1. 섬마다 번호를 부여 << BFS로 진행
2. 번호가 부여된 섬마다 BFS_Load 진행을 통해 우선순위 큐에 경로를 넣어준다.
3. 최종적으로 스패닝 알고리즘을 이용하여 최소값을 찾아주었다.
조심해야 될점은 다리의 최소길이는 2 << 라는 점이다.
시간복잡도를 계산해 봤을때 O(n^3)이 나오지만 n의 값이 100이하라 시간안에 풀 수 있다.
함수 설명
- N(행)과 M(열)의 크기를 입력받고, 2차원 벡터 arr에 지도를 저장합니다.
- newMap은 연결된 영역을 식별하는 새로운 지도입니다.
2. BFS로 영역 구분 (BFS_setNumer 함수)
- BFS_setNumer는 BFS를 사용하여 지도에서 섬(1로 이루어진 구역)을 탐색하고, 각 섬을 서로 다른 숫자로 구분합니다.
- 탐색할 때 큐 myQueue를 사용해 각 노드를 방문하고, 4방향으로 인접한 노드로 이동하면서 연결된 섬을 하나의 숫자로 식별합니다.
- 연결된 섬을 모두 탐색하면 mapCount를 증가시킵니다.
3. 다리 생성 (goTo 함수)
- goTo 함수는 특정 방향으로 다리를 건설할 수 있는지 확인하는 역할을 합니다. 즉, 현재 섬에서 다른 섬으로 다리를 놓을 수 있는 경우 그 거리를 계산합니다.
- 다리를 놓을 수 있는 경우, 우선순위 큐 pq에 그 다리 정보를 추가합니다. 다리의 길이가 2 이상이어야만 유효한 다리로 인정됩니다.
4. 모든 섬에서 다리 연결 가능성 확인 (BFS_findLoad 함수)
- 각 섬에서 가능한 다리들을 확인하기 위해 BFS_findLoad가 실행됩니다.
- 4방향(상, 하, 좌, 우)으로 탐색하며 섬 간 연결을 확인하고, 연결 가능 시 다리 정보를 우선순위 큐에 추가합니다.
5. 최소 스패닝 트리 (SpanningTree 함수)
- 우선순위 큐에서 가장 짧은 다리부터 연결을 시도합니다.
- Union-Find 알고리즘을 통해 다리가 서로 다른 두 섬을 연결하는 경우에만 다리를 연결합니다.
- 다리를 연결할 때마다 결과 값에 다리의 길이를 추가하여 총 다리 길이를 계산합니다.
[소스 코드]
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int dy[4] = { 0,-1,0,1 };
int dx[4] = { 1,0,-1,0 };
typedef pair<int, int> Node;
typedef struct Edge {
int sero1;
int garo1;
int sero2;
int garo2;
int weight;
};
struct cmp {
bool operator()(Edge a, Edge b) {
return a.weight > b.weight;
}
};
int N, M;
vector<vector<int>> arr;
vector<vector<int>> newMap;
priority_queue<Edge, vector<Edge>, cmp>pq;
vector<int> parent;
int mapCount = 1;
int resultCount = 0;
int find(int a) {
if (a == parent[a])return a;
return parent[a] = find(parent[a]);
}
void Union(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
parent[b] = a;
}
}
bool isSame(int a, int b) {
a = find(a);
b = find(b);
if (a == b)return true;
return false;
}
bool isInside(int sero, int garo) {
if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
return false;
}
void Input() {
cin >> N >> M;
arr.resize(N);
for (int i = 0; i < N; i++) {
arr[i].resize(M);
}
newMap = arr;
for (int i = 0; i < N; i++) {
for (int k = 0; k < M; k++) {
cin >> arr[i][k];
}
}
}
void BFS_setNumer(int sero, int garo) {
vector<vector<bool>> visited;
visited.resize(N);
for (int i = 0; i < N; i++) {
visited[i].resize(M, false);
}
queue<Node> myQueue;
myQueue.push({sero,garo});
visited[sero][garo] = true;
newMap[sero][garo] = mapCount;
while (!myQueue.empty()) {
int nowSero = myQueue.front().first;
int nowGaro = myQueue.front().second;
myQueue.pop();
for (int i = 0; i < 4; i++) {
int nextSero = nowSero + dy[i];
int nextGaro = nowGaro + dx[i];
if (isInside(nextSero, nextGaro) == false)continue;
if (visited[nextSero][nextGaro] == true)continue;
if (arr[nextSero][nextGaro] == 1) {
myQueue.push({ nextSero,nextGaro });
visited[nextSero][nextGaro] = true;
newMap[nextSero][nextGaro] = mapCount;
}
}
}
mapCount++;
}
void goTo(int dy, int dx, int sero, int garo) {
int nowSero = sero;
int nowGaro = garo;
int nowNumber = newMap[nowSero][nowGaro];
int count = 0;
while (1) {
int nextSero = nowSero + dy;
int nextGaro = nowGaro + dx;
if (isInside(nextSero, nextGaro) == false)return;
int nextNumber = newMap[nextSero][nextGaro];
if (nowNumber == nextNumber)return;
if (nextNumber != 0 && nextNumber != nowNumber) {
pq.push({ sero,garo,nextSero,nextGaro,count });
return;
}
nowSero = nextSero;
nowGaro = nextGaro;
count++;
}
}
void BFS_findLoad(int sero, int garo) {
int nowSero = sero;
int nowGaro = garo;
for (int i = 0; i < 4; i++) {
goTo(dy[i], dx[i], sero, garo);
}
}
void SpanningTree() {
parent.resize(mapCount);
for (int i = 0; i < mapCount; i++) {
parent[i] = i;
}
while (!pq.empty()) {
int nowSero = pq.top().sero1;
int nowGaro = pq.top().garo1;
int nextSero = pq.top().sero2;
int nextGaro = pq.top().garo2;
int weight = pq.top().weight;
pq.pop();
if (weight < 2)continue;
int nowNumber = newMap[nowSero][nowGaro];
int nextNumber = newMap[nextSero][nextGaro];
if (isSame(nowNumber, nextNumber) == true)continue;
Union(nowNumber, nextNumber);
resultCount += weight;
}
}
void GameStart() {
for (int i = 0; i < N; i++) {
for (int k = 0; k < M; k++) {
if (arr[i][k] == 1 && newMap[i][k] == 0) {
BFS_setNumer(i, k);
}
}
}
for (int i = 0; i < N; i++) {
for (int k = 0; k < M; k++) {
if (newMap[i][k] != 0) {
BFS_findLoad(i, k);
}
}
}
SpanningTree();
bool flag = false;
for (int i = 1; i < mapCount; i++) {
if (isSame(parent[1], parent[i]) == false) {
flag = true;
}
}
if (flag == true) {
cout << -1;
}
else {
cout << resultCount;
}
}
void Print() {
cout << '\n';
for (int i = 0; i < N; i++) {
for (int k = 0; k < M; k++) {
cout << newMap[i][k] << " ";
}
cout << '\n';
}
while (!pq.empty()) {
cout << pq.top().weight << " ";
}
}
int main(void) {
Input();
GameStart();
}