![[C++]백준 - 17472번 문제](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FdwAfLZ%2FbtrjQJT7O1x%2FXHD4NZVFoNCpWW7vfbhf6K%2Fimg.jpg)
17472번: 다리 만들기 2 (acmicpc.net)
17472번: 다리 만들기 2
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.
www.acmicpc.net
17472번 : 다리 만들기 2
섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다.
섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다.
다리는 바다에만 건설할 수 있고, 다리의 길이는 다리가 격자에서 차지하는 칸의 수이다. 다리를 연결해서 모든 섬을 연결하려고 한다. 섬 A에서 다리를 통해 섬 B로 갈 수 있을 때, 섬 A와 B를 연결되었다고 한다. 다리의 양 끝은 섬과 인접한 바다 위에 있어야 하고, 한 다리의 방향이 중간에 바뀌면 안된다. 또, 다리의 길이는 2 이상이어야 한다.
다리의 방향이 중간에 바뀌면 안되기 때문에, 다리의 방향은 가로 또는 세로가 될 수 밖에 없다. 방향이 가로인 다리는 다리의 양 끝이 가로 방향으로 섬과 인접해야 하고, 방향이 세로인 다리는 다리의 양 끝이 세로 방향으로 섬과 인접해야 한다.
섬 A와 B를 연결하는 다리가 중간에 섬 C와 인접한 바다를 지나가는 경우에 섬 C는 A, B와 연결되어있는 것이 아니다.
아래 그림은 섬을 모두 연결하는 올바른 2가지 방법이고, 다리는 회색으로 색칠되어 있다. 섬은 정수, 다리는 알파벳 대문자로 구분했다.
다음은 올바르지 않은 3가지 방법이다
다리가 교차하는 경우가 있을 수도 있다. 교차하는 다리의 길이를 계산할 때는 각 칸이 각 다리의 길이에 모두 포함되어야 한다. 아래는 다리가 교차하는 경우와 기타 다른 경우에 대한 2가지 예시이다.
나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자.
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다.
- 1 ≤ N, M ≤ 10
- 3 ≤ N×M ≤ 100
- 2 ≤ 섬의 개수 ≤ 6
출력
모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든 섬을 연결하는 것이 불가능하면 -1을 출력한다.
생각해 볼 점
기본적으로는 최소 스패닝 트리를 만드는 문제입니다.
그런데, 간선과 섬의 정보를 알아내는 데에 성가신 구현과 여러 알고리즘이 필요합니다.
저는 차근차근 차례대로 구현해나갈 것입니다.
우선 단계별로 다음과 같이 목표를 잡습니다.
1. 섬들을 찾고, 해당 섬들에 번호를 붙여 노드처럼 사용하기
2. 섬들끼리 연결 가능한 모든 간선을 찾기
3. 최소 스패닝 트리를 이용해 최소값을 출력하기
1번부터 시작합니다.
이중 포문을 이용해 지도 정보를 전부 탐색합니다.
도중에 육지가 나타나면, BFS 알고리즘 혹은 DFS 알고리즘을 이용해 탐색합니다.
지도 정보에서 바다는 0, 육지는 1로 표기하고 있으므로 저는 섬의 번호를 2번부터 붙이겠습니다.
즉, 지도에서 0 = 바다, 1 = 탐색되지 않은 육지, 2 이상 = 탐색이 완료된 섬
이라고 정의하겠습니다.
BFS나 DFS를 수행하면서 지도 정보를 모두 갱신하고, 다른 모든 섬 역시 같은 방법으로 탐색합니다.
섬이 모두 탐색되었다면, 이제 2번으로 넘어가겠습니다.
모든 간선을 탐색할 때에는 다음과 같이 수행합니다.
지도 정보를 수평/ 수직방향으로 모두 검사하여 연결할 수 있는 다리는 모두 연결합니다.
탐색 과정에서 A 섬과 B 섬을 만났으면, 간선을 생성합니다.
만약 A섬과 B섬의 간선이 이미 있다면, 더 짧은 길이를 가진 간선으로 교체합니다.
또한, 간선의 길이가 1을 초과하지 않으면 무시합니다.
이제 모든 간선을 생성했기 때문에, 3번으로 넘어갑니다.
크루스칼 알고리즘을 이용하여 최소 스패닝 트리의 최소 비용을 출력합니다.
코드
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
struct edge
{
int a, b, length;
};
const int move_x[4] = {-1, 1, 0, 0};
const int move_y[4] = {0, 0, -1, 1};
bool sorting(edge a, edge b)
{
return a.length < b.length;
}
//부모를 찾는 함수
int get_parent(int parent[], int target)
{
if(parent[target] == target) return target;
return parent[target] = get_parent(parent, parent[target]);
}
//유니온 파인드 함수
bool make_union(int parent[], edge e)
{
int a = get_parent(parent, e.a);
int b = get_parent(parent, e.b);
if(a == b) return false;
parent[b] = a;
return true;
}
//BFS 알고리즘을 통해 섬에 번호를 붙임
void BFS(int **map, int N, int M, int y, int x, int num)
{
queue<pair<int, int>> q;
q.push({y, x});
map[y][x] = num;
while(!q.empty())
{
pair<int, int> current = q.front();
q.pop();
for(int i = 0; i < 4; i++)
{
int next_x = current.second + move_x[i];
int next_y = current.first + move_y[i];
if(next_x < 0 || M - 1 < next_x || next_y < 0 || N - 1 < next_y) continue;
if(map[next_y][next_x] == 1)
{
q.push({next_y, next_x});
map[next_y][next_x] = num;
}
}
}
}
int main()
{
int N, M; //세로 , 가로
scanf("%d %d", &N, &M);
//입력부
int **map = new int*[N];
for(int i = 0; i < N; i++)
{
map[i] = new int[M];
for(int j = 0; j < M; j++) scanf("%d", &map[i][j]);
}
int island_number = 2; //0, 1은 각각 바다와 섬이므로 2부터 시작
//섬이 발견되면 BFS 함수를 호출해서 섬에 번호를 붙임
for(int i = 0; i < N; i++)
{
for(int j = 0; j < M; j++)
{
if(map[i][j] == 1)
{
BFS(map, N, M, i, j, island_number);
island_number++;
}
}
}
island_number -= 2;
int **graph = new int*[island_number];
int *parent = new int[island_number];
for(int i = 0; i < island_number; i++)
{
graph[i] = new int[island_number];
parent[i] = i;
fill_n(graph[i], island_number, 100);
}
vector<edge> v;
//지도를 탐색하여 모든 가로 브릿지 생성
for(int i = 0; i < N; i++)
{
edge e = edge();
e.length = 0;
bool bridge_making = false;
for(int j = 0; j < M; j++)
{
if(!map[i][j]) e.length++;
else
{
if(!bridge_making)
{
bridge_making = true;
e.a = map[i][j] - 2;
}
else if(map[i][j] != e.a + 2)
{
if(e.length < graph[e.a][map[i][j] - 2])
{
e.b = map[i][j] - 2;
if(1 < e.length)
{
graph[e.a][e.b] = e.length;
graph[e.b][e.a] = e.length;
v.push_back(e);
}
}
e.a = e.b;
}
e.length = 0;
}
}
}
//모든 세로 브릿지 생성
for(int j = 0; j < M; j++)
{
edge e = edge();
e.length = 0;
bool bridge_making = false;
for(int i = 0; i < N; i++)
{
if(!map[i][j]) e.length++;
else
{
if(!bridge_making)
{
bridge_making = true;
e.a = map[i][j] - 2;
}
else if(map[i][j] != e.a + 2)
{
if(e.length < graph[e.a][map[i][j] - 2])
{
e.b = map[i][j] - 2;
if(1 < e.length)
{
graph[e.a][e.b] = e.length;
graph[e.b][e.a] = e.length;
v.push_back(e);
}
}
e.a = e.b;
}
e.length = 0;
}
}
}
sort(v.begin(), v.end(), sorting);
//크루스칼 알고리즘
int result = 0;
int num_of_edge = 0;
for(edge e : v)
{
if(make_union(parent, e))
{
result += e.length;
num_of_edge++;
}
}
if(num_of_edge != island_number - 1) result = -1;
printf("%d", result);
for(int i = 0; i < island_number; i++) delete[] graph[i];
for(int i = 0; i < N; i++) delete[] map[i];
delete[] map;
delete[] graph;
delete[] parent;
return 0;
}
그 외
'공부 및 정리 > 백준 코드' 카테고리의 다른 글
| [C++]백준 - 1094번 문제 (0) | 2021.11.05 |
|---|---|
| [C++]백준 - 2098번 문제 (0) | 2021.11.04 |
| [C++]백준 - 1311번 문제 (0) | 2021.11.03 |
| [C++]백준 - 2357번 문제 (0) | 2021.11.03 |
| [C++]백준 - 11505번 문제 (0) | 2021.11.01 |