[BOJ][Python] 2146번 다리 만들기

1. 문제

https://www.acmicpc.net/problem/2146

백준 2146 - 다리 만들기 문제 캡쳐

N X N 사이즈의 지도를 입력을 받게 되는데, 이 때 바다를 0, 육지를 1로 나타내고 섬은 바다로 둘러쌓인 영역 각각을 의미하게 된다. 이때 섬 두개를 잇는 가장 짧은 다리의 길이를 구해야한다. 다리는 가장 짧게 만들 수 있는 두 섬에 한하여 만들면 된다.

 

---

2. 문제 풀이 알고리즘

문제풀이 알고리즘

예제의 입력을 보면 섬들의 육지 영역은 모두 1로만 표시되어 있어서 임의의 육지 영역 하나를 골랐을 때 이 영역이 어떤 섬의 땅인지 구분할 수가 없다. 하지만 서로 다른 두 섬을 연결하는 다리를 만들어야해서 육지 영역을 어떤 섬의 것인지 구분해주어야 한다.

 

그래서 처음으로 구현할 것은 섬 영역을 나누어주는 것이다. 육지 영역을 1이라는 숫자로 통일하게 입력받았기 때문에 가운데 그림과 같이 2부터 시작하여 같은 섬의 영역이면 같은 숫자를 넣어주고 다른 섬의 영역으로 넘어가게 되었을 때는 숫자를 하나씩 늘려 구분해주었다.

 

이렇게 섬의 영역을 모두 구분하고 난 이후, 각 섬의 테두리 영역을 점점 늘려가며 가장 처음으로 다른 섬의 테두리와 접하게 되었을 때가 다리의 길이가 최소가 될 때와 같게 되므로, 이때의 테두리를 늘린 횟수를 출력해주었다.

 

---

3. 구현

1) 섬 영역 구분하기, 테두리 영역 저장(bfs)

import sys
from collections import deque

n = int(sys.stdin.readline().strip())
area = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(n)]
visited = [[0 for _ in range(n)] for _ in range(n)]
visited_from = [[[0, 0] for _ in range(n)] for _ in range(n)]
area_end = deque()

#섬 영역 나누기
def indexing_area():
    area_cnt = 2
    for i in range(n):
        for j in range(n):
            if area[i][j] == 0 or visited[i][j] == 1:
                visited[i][j] = 1
                continue

            queue = deque()
            queue.append([i, j])
            visited[i][j] = 1

            while queue:
                row, col = queue.popleft()
                area[row][col] = area_cnt
                visited[row][col] = 1

                cnt = 0

                if row > 0:
                    if area[row - 1][col] == 0:
                        cnt += 1

                if col < n - 1:
                    if area[row][col + 1] == 0:
                        cnt += 1

                if col > 0:
                    if area[row][col - 1] == 0:
                        cnt += 1
                if row < n-1:
                    if area[row + 1][col] == 0:
                        cnt += 1

                if cnt > 0:
                    area_end.append([row, col])
                    visited_from[row][col] = [area_cnt, 0]



                for next in [[row, col + 1],[row - 1, col], [row, col - 1],[row + 1, col]]:
                    if 0<= next[0] < n and 0<= next[1] < n:
                        if visited[next[0]][next[1]] == 0 and area[next[0]][next[1]] == 1:
                            queue.append(next)
                            visited[next[0]][next[1]] = 1

            area_cnt += 1

섬영역을 나누기 위한 함수에서는 칸 하나씩을 보면서 육지 영역에 해당하는 부분(area[row][col] == 1)이 나왔을 때, 그 부분부터 bfs를 사용하여 같은 섬 영역인 부분을 찾아주었다.

 

해당 좌표의 좌, 우, 위, 아래 중 1인 부분을 queue에 넣어주고 한 번 거쳐간 부분이므로 visited를 1로 해주었다. 영역을 넓혀가면서 같은 섬인것을 표시하기위한 area_cnt를 area[row][col] 자리에 넣어주었다. 탐색이 모두 끝나면 해당 섬에 대한 영역을 모두 훑은 것이기 때문에 area_cnt를 증가시켜주었다.

 

그리고 이 과정에서 테두리부분만을 찾아 area_end에 넣어 다음에 테두리를 늘리며 최단 거리를 찾을 때도 용이하게 하였다. area_end에는 테두리에 해당하는 좌표 [row, col]를 넣어주었고 테두리를 늘리며 최단거리를 찾을 때 사용할 visited_from에는 테두리의 좌표에 [섬 구분 숫자, 0(테두리를 아직 늘려주기 전 상태)]를 넣어 주었다.

 

2) 테두리 늘리면서 다리의 최단거리 찾기(bfs)

def bfs():
    min = 200
    flag = 0
    while area_end:
        row, col = area_end.popleft()
        if flag == 1 and min < visited_from[row][col][1] * 2:
            break

        for next in [[row - 1, col], [row, col + 1], [row, col - 1],[row + 1, col]]:
            i, j = next
            if 0<= i < n and 0<= j < n:
                if visited_from[i][j][0] == 0 and area[i][j] == 0:
                    area_end.append([i, j])
                    visited_from[i][j] = [visited_from[row][col][0], visited_from[row][col][1] + 1]
                    continue

                if visited_from[i][j][0] != 0 and visited_from[i][j][0] != visited_from[row][col][0]:
                    flag = 1
                    if min > visited_from[row][col][1] + visited_from[i][j][1]:
                        min = visited_from[row][col][1] + visited_from[i][j][1]

    if flag == 0:
        print(0)
    else:
        print(min)
                    

indexing_area()
bfs()

테두리를 늘리며 영역을 찾을 때는 위에서 만든 area_end, visited_from을 사용하였다.

 

area_end에서 테두리의 좌표를 뽑아 좌, 우, 위, 아래 중에서 섬 안쪽에 해당하지 않은 부분(area[i][j] == 0)을 찾아 그 때의 좌표를 area_end에 넣어주고 해당 부분이 어떤 섬으로부터 왔는지와 이전보다 하나 증가한 길이를 해당 좌표의 vistied_from에 넣어주는 과정을 반복해주었다.

 

이 과정을 반복하다보면 늘어난 테두리 중 서로 다른 섬으로부터 온 테두리끼리 만나게 되는데 그 때의 테두리 길이를 더하여 최솟값 min에 넣어주었다. flag는 겹치는 테두리를 찾은시점부터 같은 레벨을 돌면서 다리의 최소 길이를 완전히 찾기 위해 만들어주었다.