Problem 문제풀이
DFS와 UNION FIND를 동시에 물어보는 깔끔한 문제였다. 풀이는 다음과 같다.
전략
-
DFS로 지도를 돌면서 섬을 numbering한다. -
지도를 다시 탐색하면서 다리를 지을 수 있는 장소를 알아본다.
-
만약 다리를 지을 수 있고 두 섬이 연결되어 있지 않으면 연결을 하는 경우와 연결하지 않는 경우로 분기한다.
-
모든 섬이 연결되었을 때 다리의 길이의 최솟값을 구한다.
차근차근 풀면 누구나 풀 수 있는 문제이다. 먼저 DFS를 구현해보자.
void dfs(int r, int c)
{
visited[r][c] = island_size;
for (int i = 0; i < 4; i++)
{
int nR = r + dirR[i];
int nC = c + dirC[i];
if (nR >= 0 && nR < N && nC >= 0 && nC < M)
{
if (visited[nR][nC] == 0 && island[nR][nC]==1)
{
dfs(nR, nC);
}
}
}
}
numbering 작업을 끝냈다. 이제 본격적으로 문제를 풀어보자.
우리는 다리를 건축하는 함수 build를 만들 것이다. build의 매개변수는 다음과 같다.
void build(int sum, int r, int c, int *parent);
첫 번째 매개변수는 여태까지 누적된 다리의 길이이다.
두 번째, 세 번째 매개변수는 검사할 좌표를 담고 있다.
마지막 매개변수는 섬과 섬의 상태를 담고 있는 배열을 넘긴다.
마지막 매개변수가 핵심인데 섬 A와 섬 B에 다리를 놓을 수 있을 경우
A와 B를 Union한 뒤 다시 (0, 0)에서 검사를 시작할 것이다. 코드는 다음과 같다.
void build(int sum, int r, int c, int *parent)
{
if (Check(parent))
{
if (answer == -1 || answer > sum)
{
answer = sum;
}
return;
}
for (int i = r; i < N; i++)
{
for (int j = (i==r)?c:0; j < M; j++)
{
if (visited[i][j] != 0)
{
for (int d = 0; d < 4; d++)
{
int nI = i + dirR[d];
int nJ = j + dirC[d];
if (nI >= 0 && nI < N && nJ >= 0 && nJ < M)
{
if (visited[nI][nJ] == 0)
{
int cnt = 0;
while (visited[nI][nJ] == 0)
{
nI = nI + dirR[d];
nJ = nJ + dirC[d];
if (nI >= 0 && nI < N && nJ >= 0 && nJ < M)
{
cnt++;
}
else
{
cnt = 0;
break;
}
}
if (cnt >= 2 && visited[nI][nJ]!=visited[i][j])
{
int x = Find(visited[i][j], parent);
int y = Find(visited[nI][nJ], parent);
if (x != y)
{
int* newParent = new int[island_size+1];
for (int i = 0; i <= island_size; i++)
{
newParent[i] = parent[i];
}
newParent[x] = y;
build(sum+cnt, i, j,newParent);
}
}
}
}
}
}
}
}
}
갑자기 전체 코드가 등장해서 당황스러울 것이다. 조금씩 뜯어서 살펴보자.
먼저 제일 위에 있는 체크 함수는 모든 섬이 연결되어 있는지 확인하는 함수이다.
bool Check(int* parent)
{
for (int i = 2; i <= island_size; i++)
{
if (Find(i - 1, parent) != Find(i, parent))
{
return false;
}
}
return true;
}
만약 모든 섬이 연결되어 있다면 answer를 갱신하고 return하면 된다. 더 연결해야할 경우 (r,c)에서
검사를 시작한다. visited 배열에는 현 위치의 섬의 번호가 들어있다. 다리를 놓으려면 4방향중 바다
즉, visited가 0인 곳을 찾아야한다.
for (int j = (i==r)?c:0; j < M; j++)
{
if (visited[i][j] != 0)
{
for (int d = 0; d < 4; d++)
{
int nI = i + dirR[d];
int nJ = j + dirC[d];
if (nI >= 0 && nI < N && nJ >= 0 && nJ < M)
{
if (visited[nI][nJ] == 0)
바다를 찾았으니 다음 섬이 나올 때까지 전진한다. 만약 한 칸만에 바다가 나오거나 다음 섬을 만나지 못하고
지도의 끝에 도달하면 다리를 놓을 수 없다.
int cnt = 0;
while (visited[nI][nJ] == 0)
{
nI = nI + dirR[d];
nJ = nJ + dirC[d];
if (nI >= 0 && nI < N && nJ >= 0 && nJ < M)
{
cnt++;
}
else
{
cnt = 0;
break;
}
}
이제 마지막이다. 다리를 놓을 수 있는 경우 두 섬이 연결 되어 있는지 확인한다. 연결 되어 있지 않다면
두 섬을 연결하고 처음부터 검사를 시작한다.
if (cnt >= 2 && visited[nI][nJ]!=visited[i][j])
{
int x = Find(visited[i][j], parent);
int y = Find(visited[nI][nJ], parent);
if (x != y)
{
int* newParent = new int[island_size+1];
for (int i = 0; i <= island_size; i++)
{
newParent[i] = parent[i];
}
newParent[x] = y;
build(sum+cnt, i, j,newParent);
}
}
엄청나게 어려운 개념이 사용되는 문제는 아니었다. DFS, UNION-FIND는 우리에게 이미 익숙한 알고리즘이다. 이 둘을
적절히 섞어서 사용할 수 있는지 기본기를 묻는 좋은 문제였다. 그럼 화이팅!