[백준] 2146번 다리 만들기, bfs, 플러드필+최단거리 (Python3)

문제 설명

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

나의 첫 번째 풀이

단지 번호 붙이기(백준 2667번) + 최단 거리 구하기(백준 2178번) 두 문제를 혼합한 문제이다.

각각의 섬에 라벨을 붙여, 한 섬의 모든 면에서 다른 섬으로 갈 수 있는 모든 경우의 수를 구해서 그 중의 최단 거리를 구하는 문제이다.

distinguish()라는 함수는 플러드필 알고리즘을 사용하여 새로운 매트릭스(new_matrix)에 번호가 붙은 섬을 만들어준다.

그 후, bfs() 함수로 섬의 모든 면에서부터 다른 섬까지 최단거리를 구한다.
bfs()를 호출할 때마다 거리를 저장하는 matrix를 만들고, 다음에 가야 할 면이 다른 섬의 숫자라면 거리를 list에 저장하는 방식으로 진행한다.

섬의 모든 면에서 다른 섬까지의 거리를 모두 담은 list의 최소값을 반환한다.

import sys
from collections import deque

N = int(sys.stdin.readline())
matrix = list()

for _ in range(N):
    input_matrix = list(map(int, sys.stdin.readline().split()))
    matrix.append(input_matrix)


dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

# 섬마다 번호를 붙임
def distinguish(i, j, num):
    if 0 > i or i >= N or 0 > j or j >= N or matrix[i][j] == 0 or visited[i][j] != 0:
        return
    else:
        visited[i][j] = 1
        new_matrix[i][j] = num
        distinguish(i-1 ,j, num)
        distinguish(i+1, j, num)
        distinguish(i, j-1, num)
        distinguish(i, j+1, num)

# 거리를 구하는 함수
def bfs(i, j, map, num):
    queue = deque()
    queue.append([i, j])
    distance_matrix = [[0] * N for _ in range(N)]
    distance_matrix[i][j] = 0

    while queue:
        a, b = queue.popleft()

        for direction in range(4):
            goX = a + dx[direction]
            goY = b + dy[direction]

            if 0<= goX < N and 0<= goY < N  and distance_matrix[goX][goY] == 0:
                if map[goX][goY] == 0:
                    queue.append([goX, goY])
                    distance_matrix[goX][goY] = distance_matrix[a][b] + 1
                elif map[goX][goY] != num: # next step에 번호가 다른 곳을 만나면 현재의 거리(시작 지점에서 다른 번호까지의 거리)를 list에 삽입 후 리턴
                    dist_list.append(distance_matrix[a][b])
                    return

# 섬마다 번호가 다른 새로운 매트릭스
new_matrix = [[0] * N for _ in range(N)]
visited = [[0] * N for _ in range(N)]
cnt = 1

# distinguish로 번호 붙이는 반복문
for i in range(N):
    for j in range(N):
        if matrix[i][j] == 1 and visited[i][j] == 0:
            distinguish(i, j, cnt)
            cnt += 1
# bfs로 거리 구하는 반복문
dist_list = []
for i in range(N):
    for j in range(N):
        if new_matrix[i][j] != 0:
            bfs(i, j, new_matrix, new_matrix[i][j])

print(min(dist_list))

나의 두 번째 풀이

다리를 놓는 구간은 각 섬의 끝(엣지) 부분에서만 출발한다. 첫 번째 풀이방법에서는 엣지부분이 아닌 곳에서도 거리를 구하는 함수 bfs()를 호출하기 때문에 비효율적이라 생각했다.
그래서 엣지를 먼저 구한 뒤 엣지에서만 함수를 호출하도록 다시 코드를 짜보았다.
하지만 예상과는 다르게 메모리와 시간이 더 소요됐다.
더 효율적으로 짤 수 있는 방법을 더 고민해봐야 겠다.

import sys
sys.setrecursionlimit(1000000)
from collections import deque

N = int(sys.stdin.readline())
matrix = list()

for _ in range(N):
    input_matrix = list(map(int, sys.stdin.readline().split()))
    matrix.append(input_matrix)

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

edge = []

# 1. 각 섬의 번호를 구한 뒤 (2번부터) edge를 구해 리스트에 넣음.
def dfs(a, b, temp, island):

    matrix[a][b] = island

    for i in range(4):
        go_x = a + dx[i]
        go_y = b + dy[i]

        if 0 <= go_x < N and 0 <= go_y < N and matrix[go_x][go_y] == 0:
            temp.append([a, b])
        elif 0 <= go_x < N and 0 <= go_y < N and matrix[go_x][go_y] == 1:
            dfs(go_x, go_y, temp, island)

island = 2

for i in range(N):
    for j in range(N):
        if matrix[i][j] == 1:
            temp = []
            dfs(i, j, temp, island)
            edge.append(temp) # 각 섬의 edge를 한 리스트로 묶음
            island += 1

# 2. 모든 edge로부터 다른 섬을 만나는 모든 경우의 거리를 리스트에 담아 최소값을 구함
def flooldFill(edge, island , distance):

    visited = [[0]*N for _ in range(N)]
    queue = deque()

    queue.append(edge)

    while queue:
        a, b = queue.popleft()

        for i in range(4):
            go_x = a + dx[i]
            go_y = b + dy[i]
            if 0 <= go_x < N and 0 <= go_y < N:
                if matrix[go_x][go_y] > 1 and matrix[go_x][go_y] != island:
                    return visited[a][b]
                elif matrix[go_x][go_y] == 0 and visited[go_x][go_y] == 0:
                    visited[go_x][go_y] = visited[a][b] + 1
                    queue.append([go_x, go_y])

ans_list = []
for i in range(len(edge)):
    for j in range(len(edge[i])):
        distance = 0
        ans = flooldFill(edge[i][j], i+2 , distance)
        if ans:
            ans_list.append(ans)

print(min(ans_list))