백준 다리만들기 (dfs + bfs)

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

상하좌우로 이어진 섬에서 다른 섬으로 이동할 수 있는 최단거리를 구하는 문제다.

각 섬의 테두리에서 다른 섬의 테두리까지 도착하는 최단거리를 구하는 것으로 이해했고

이 풀이를 적용하기 위해 해야할 것은 다음과 같다.

1. 각 섬을 숫자로 마킹한다.
2. 테두리 좌표를 구해 해당 좌표에서 다른 섬의 테두리까지의 거리를 구한다.
3. 모든 섬의 테두리에서 출발해 다른 섬의 테두리에 도착할 때까지의 거리 중 최단거리를 반환한다.

1번은 dfs로 상하좌우로 이어진 부분에 대해 1,2,3.. 숫자을 더하며 마킹을 했다.
그리고 해당 좌표로부터 상,하,좌,우로 이동했을 때 그 좌표의 값이 하나라도 0에 해당한다면 테두리이므로 섬의 숫자를 키로갖는 딕셔너리에 좌표를 추가했다.

마지막으로 각 테두리좌표에서 다른 섬의 테두리좌표까지 걸리는 거리를 bfs로 구해 문제를 해결했다.

bfs를 수행할 때 visited를 사용하지 않으면 위로갔다가 다시 내려오는 중복연산이 생기기때문에 방문했던 곳은 재방문하지않도록 작성해 시간초과를 없앨 수 있다.

N = int(input())
lst = [list(map(int, input().split())) for _ in range(N)]
visited = [[False] * N for _ in range(N)]
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
import sys

sys.setrecursionlimit(10 ** 6)

def marking_island(x, y, island_number, border):  # dfs
    global lst
    if lst[x][y] == 0 or visited[x][y] == True:
        return
    lst[x][y] = island_number
    visited[x][y] = True
    for i in range(4):
        mx, my = dx[i] + x, dy[i] + y
        if 0 <= mx < N and 0 <= my < N:
            if lst[mx][my] != 0:
                marking_island(mx, my, island_number, border)
            if lst[mx][my] == 0 and [x, y] not in border[island_number]:  # 테두리
                border[island_number].append([x, y])
    return


def bfs(x, y, mov_cnt, island_number):
    q = [[x, y, mov_cnt]]
    tmp_visited = [[False] * N for _ in range(N)]
    while q:
        i, j, cnt = q.pop(0)
        if tmp_visited[i][j] == True:
            continue
        if lst[i][j] != 0 and lst[i][j] != island_number:
            return cnt - 1
        tmp_visited[i][j] = True
        for idx in range(4):
            mx, my = dx[idx] + i, dy[idx] + j
            if 0 <= mx < N and 0 <= my < N:
                if lst[mx][my] == 0 or lst[mx][my] != island_number:
                    q.append([mx, my, cnt + 1])
    return cnt


def solution(N, lst):
    island_number = 1
    answer = []
    border = {}  # island: [[테두리 좌표], [],,]
    for i in range(N):
        for j in range(N):
            if lst[i][j] != 0 and visited[i][j] == False:
                border[island_number] = []
                marking_island(i, j, island_number, border)
                island_number += 1
    for island_number in border:
        for border_loc in border[island_number]:
            x, y = border_loc
            visited[x][y] = False
            answer.append(bfs(x, y, 0, island_number))
    return min(answer)


print(solution(N, lst))