출처:https://www.acmicpc.net/problem/2146
문제
-
여러 섬으로 이루어진 나라가 있다. 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다.
-
이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다.
-
지도가 주어질 때, 가장 짧은 다리 하나를 놓아 두 대륙을 연결하는 방법을 찾으시오.
조건
- 첫 줄에는 지도의 크기 N(100이하의 자연수)가 주어진다.
- 그 다음 N줄에는 N개의 숫자가 빈칸을 사이에 두고 주어지며, 0은 바다, 1은 육지를 나타낸다. 항상 두 개 이상의 섬이 있는 데이터만 입력으로 주어진다.
풀이
문제는 전형적이지만, 구현자체는 만만하지 않은 문제이다. 잘못하면 생각의 늪에 빠져 여러가지 경우를 고려하지 못하고 시간만 보낼 확률이 높다.
첫번째 생각) 섬의 경계점을 다 넣고, 섬의 경계점에서 다른 섬의 경계점을 방문하는 로직을 짜보자.
- 문제점 : 섬과 섬을 구분할 어떤 값이 필요하다. 그럴려면, 결국 모든 섬을 구분할 수 있는 로직이 들어가야하는데, 이렇게되면 모든 경계점을 구하는 의미가 무색해진다.
두번째 생각) 모든 섬을 구분할 수 있게, Labeling을 진행하자. 그 다음, 경계점에서 다른 섬의 경계점을 방문해보자.
- 경계점을 직접 다 구할 필요가 없었다. 우리가 관심있는건 결국,
다른 섬영역이므로, 모든 점에 대해서 BFS를 해주는 것이 아니라, 바다와 맞닿아있는 점만 BFS를 돌려야한다. 따라서, 일단 섬의 모든 좌표를 넣고,인접한 바다좌표을 단순히 IF문으로 구분하여, 계속 Queue에 넣어서 BFS를 진행하는 방식으로 하면 된다. 그리고, 만약 바다가 아니고, 자기 자신의 라벨링된 섬도 아니라면 다른 섬에 도착한 것이므로 거리를 반환한다.
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define X first
#define Y second
using namespace std;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
int N;
int ans = INT_MAX;
int Island[101][101];
int number_Island[101][101];
bool visited[101][101];
bool outOfRange(int x, int y)
{
return (x < 0 || x >= N || y < 0 || y >= N);
}
void label_Island(int start_x, int start_y, int cnt)
{
queue<pair<int, int>> Q;
Q.push({start_x, start_y});
while (!Q.empty())
{
pair<int, int> cur = Q.front();
Q.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.first + dx[dir];
int ny = cur.second + dy[dir];
if (outOfRange(nx, ny))
continue;
if (Island[nx][ny] == 0 || number_Island[nx][ny] != 0)
continue;
number_Island[nx][ny] = cnt;
Q.push({nx, ny});
}
}
}
int make_bridge(int label)
{
queue<pair<int, int>> Q;
// 모든 라벨링된 점에 대해서 탐색한다.
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (number_Island[i][j] == label)
{
visited[i][j] = true;
Q.push({i, j});
}
}
}
int dist = 0;
// Q가 비워질때 까지
while (!Q.empty())
{
// Q에 있는 것들을 비워야하지만, 동시에 탐색하면서 Queue에 쌓여야한다.
// 다른 섬 까지 닿아야하기 때문
int curSize = Q.size();
for (int i = 0; i < curSize; i++)
{
pair<int, int> cur = Q.front();
Q.pop();
for (int dir = 0; dir < 4; dir++)
{
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (outOfRange(nx, ny))
continue;
// 바다가 아니라, 다른 육지에 도착한다면 거리를 반환
if (number_Island[nx][ny] != 0 && number_Island[nx][ny] != label)
{
return dist;
}
// 탐색하는 곳이 방문하지않은 바다 칸이라면 , 칸에 넣고, 방문표시.
if (!visited[nx][ny] && number_Island[nx][ny] == 0)
{
visited[nx][ny] = true;
Q.push({nx, ny});
}
}
}
dist++;
}
}
int main()
{
fastio;
cin >> N;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> Island[i][j];
}
}
int cnt = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
// 육지이고, 방문을 하지 않았다면
if (Island[i][j] && number_Island[i][j] == 0)
{
cnt++;
number_Island[i][j] = cnt;
label_Island(i, j, cnt);
}
}
}
// labeling 된 친구들을 기점으로 BFS를 해주어야한다.
for (int i = 1; i <= cnt; i++)
{
memset(visited, false, sizeof(visited));
ans = min(ans, make_bridge(i));
}
cout << ans << '\n';
return 0;
}
