문제
첫인상
0. 다리를 최소로 놓아 모든 섬을 연결하는 문제다.
여기서 최소란 다리 개수가 아닌 다리의 길이를 의미한다.
1. 다리의 제약조건
- 길이가 2 이상
- 꺾이면 안 된다.
- 한 땅에 두 개 이상의 다리 놓는 거 가능
2. 다리의 시작은 어떻게?
처음 생각: 그림대로라면 섬의 양 가쪽에 있는 땅으로부터 시작하는 게 낫다. 근데 섬의 양 가쪽을 어떻게 판별할 것인가에 대한 문제를 해결해야 한다.
문제를 해결한 생각: 모든 땅덩어리에 다리를 놓는 것으로부터 시작하도록 하자. 그 후 다리를 놓을 수 있는지 확인하는 함수에 제약 조건을 두도록 하자.
3. N개 중 M개를 고르는 문제인가?
M이 정해져있지 않다. 그러므로 모든 경우의 수를 조사해야 한다.
문제 접근
문제 흐름
- 모든 땅덩어리의 좌표를 모은다. (Nodes)
- 첫 땅덩어리부터 시작하여 모든 경우의 수를 탐색하도록 한다. (상하좌우 방향 포함)
- 특정 node에서 dir 방향으로 다리를 놓을 수 있는 경우, dfs 함수를 호출한다.
- 섬의 최소 개수는 2개이므로 1개 이상의 다리가 놓인 경우 섬이 모두 연결되어 있는지 확인한다. (is_all_connected())
- 섬이 모두 연결되어 있다면 현재까지 놓은 다리 길이의 최솟값을 구한다.
추가로 ) 맨 처음 입력받은 땅부터 다리를 놓는 걸 시도하기 때문에 방향 확인을 오른쪽, 아래쪽만 할 경우 그리디하게 탐색할 수 있다. (구현하지 않은 부분이지만 다른 풀이를 참고하다 발견)
즉, 다리를 중복해서 놓는 경우를 피할 수 있음. 나는 중복해서 놓는 경우가 발생한다는 걸 알았지만 어차피 최소 다리의 수를 구하는 문제이기 때문에 이 부분을 그냥 두었는데 방향 부분을 수정하면 최적화가 가능함.
관건0. 섬 구별하기
구현: set_num()
알고리즘: BFS
섬을 구별할 필요가 있다.
섬 구별은 섬마다 map에 번호를 입력하는 것을 통해 구현.
(1) 다리를 놓는 시뮬레이션을 할 때 같은 섬에 다리를 놓는 경우를 판별할 수 있어야 하고
(2) 다리를 놓은 후 모든 섬이 연결되어 있는지 확인해야 하기 때문이다.
관건1. 다리를 놓는 가능한 지점
땅이 있는 좌표에서 모두 시작하되, 다리를 상하좌우로 놓는 상황을 모두 고려하도록 했다.
관건2. valid한 다리인지
구현: make_bridge()
이 문제에서 가장 복잡한 부분이었던 것 같다.
어떤 땅(node) 에서 dir 방향으로 다리를 놓고자 할 경우, 해당 dir로 계속해서 다리를 놓는 시뮬레이션을 돌린다.
계속해서 다리를 구축하다가
(1) 땅을 만나지 못하고 범위를 벗어날 경우
(2) 땅을 만났지만, 동일한 섬에 연결하려는 경우
(3) 다리를 다 놓았지만 길이가 2가 안 될 경우
다리 구축을 실패한다.
즉, 길이가 2 이상인 지점에서 다른 섬을 만났을 때 다리를 놓을 수 있다.
다리 구축을 실패하지 않을 경우, 연결할 땅의 정보를 반환해서 Connected 벡터에 정보를 입력했다.
(Conntected 벡터는 연결된 땅에 대한 정보를 가지는 양방향 그래프이다.)
관건3. 섬이 다 연결되어 있는지
구현: is_all_connected()
알고리즘: BFS
1번 섬을 큐에 넣고, Connected 벡터에 저장된 정보를 이용해 BFS를 돌렸다.
함수 내에서 is_visit 배열을 선언하여 연결된 섬 정보를 저장한다.
is_visit 배열이 모두 1일 경우 모든 섬이 연결된 것을 의미한다.
관건4. dfs의 save/restore
dfs 함수 호출 전후로 무엇을 save/restore 할지 정해야 한다.
(1) 연결된 섬 정보
(2) 현재까지 연결한 다리 길이
에 대한 정보를 업데이트 해주는 함수 (save_state(), restore_state()) 를 구현하여 해결.
풀이
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <limits.h>
using namespace std;
typedef struct node {
int x;
int y;
} node;
int N, M, rst, Len, LenSum;
int map[10][10];
vector<node> Nodes;
vector<int> Connect[7]; // 1~ 6;
int dx[] = { 0, -1, 0, 1 };
int dy[] = { 1, 0, -1, 0 };
int Num;
bool valid_once;
void input() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> map[i][j];
if(map[i][j] != 0) Nodes.push_back({ i, j });
}
}
LenSum = 0;
rst = INT_MAX;
valid_once = false;
}
int is_range(int x, int y) {
if (x >= 0 && x < N && y >= 0 && y < M) return true;
return false;
}
void set_num() {
int num = 0;
int is_visit[10][10];
int nmap[10][10];
memset(is_visit, 0, sizeof(is_visit));
memset(nmap, 0, sizeof(nmap));
queue<pair<int, int>> Q;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] && !is_visit[i][j]) {
is_visit[i][j] = 1;
Q.push(make_pair(i, j));
num++;
while (!Q.empty()) {
int x = Q.front().first;
int y = Q.front().second;
nmap[x][y] = num;
Q.pop();
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (map[nx][ny] == 1 && !is_visit[nx][ny] && is_range(nx, ny)) {
is_visit[nx][ny] = 1;
Q.push(make_pair(nx, ny));
}
}
}
}
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
map[i][j] = nmap[i][j];
}
}
Num = num;
}
int make_bridge(int node, int dir) {
int len = 0;
int x = Nodes[node].x;
int y = Nodes[node].y;
int Nstart = map[Nodes[node].x][Nodes[node].y];
while (true) {
int nx = x + dx[dir];
int ny = y + dy[dir];
x = nx; y = ny;
if (!is_range(nx, ny)) return -1; // 범위를 벗어날 경우
if (map[nx][ny] == Nstart) return -1; // 같은 섬에 다리를 연결할 경우
if (map[nx][ny] != 0) { // 다른 섬을 만남
if (len == 1) return -1; // 길이가 2가 안 될 경우
else { //길이가 2가 될 경우
Len = len;
return map[nx][ny];
}
}
len++;
}
}
int is_all_connected() {
int is_visit[7] = { 0, };
queue<int> Q;
is_visit[1] = 1;
Q.push(1);
while (!Q.empty()) {
int node = Q.front(); Q.pop();
for (int i = 0; i < Connect[node].size(); i++) {
if (!is_visit[Connect[node][i]]) {
is_visit[Connect[node][i]] = 1;
Q.push(Connect[node][i]);
}
}
}
for (int i = 1; i <= Num; i++) {
if (!is_visit[i]) return false;
}
return true;
}
void save_state(int current_node, int next_node, int len) {
LenSum += len;
Connect[current_node].push_back(next_node);
Connect[next_node].push_back(current_node);
}
void restore_state(int current_node, int next_node, int len) {
LenSum -= len;
Connect[current_node].pop_back();
Connect[next_node].pop_back();
}
void dfs(int node, int dir) { // i번째 땅에서 d라는 dir로 다리를 놓으려고 한다.
if (is_all_connected()) {
valid_once = true;
rst = min(LenSum, rst);
return;
}
for (int i = node + 1; i < Nodes.size(); i++) {
for (int dir = 0; dir < 4; dir++) {
int current_node = map[Nodes[i].x][Nodes[i].y];
int next_node = make_bridge(i, dir);
if (next_node != -1) {
int len = Len;
save_state(current_node, next_node, len);
dfs(i, dir);
restore_state(current_node, next_node, len);
}
}
}
}
void solve() {
set_num();
for (int i = 0; i < Nodes.size(); i++) {
for (int dir = 0; dir < 4; dir++) {
int current_node = map[Nodes[i].x][Nodes[i].y];
int next_node = make_bridge(i, dir);
if (next_node != -1) {
int len = Len;
save_state(current_node, next_node, len);
dfs(i, dir);
restore_state(current_node, next_node, len);
}
}
}
if (!valid_once) rst = -1;
}
int main() {
input();
solve();
cout << rst << endl;
}무려 177줄,, 생각보다 구현할 게 많았던 문제.
