다리 만들기 ( 2146 번 )

2146번: 다리 만들기

 

---

🧠 알고리즘

• BFS + 다익스트라(Dijkstra)를 활용한 섬 간 최단 다리 길이 탐색

 

✔️ 동작 방식

• 문제 핵심 아이디어
  
  • 각 섬을 서로 다른 번호로 구분한 뒤,
    각 섬의 가장자리 육지에서 바다를 건너 다른 섬까지의 최소 거리를 다익스트라로 구한다.

1. 섬 라벨링 ( BFS )
   • 값이 1인 육지를 BFS로 탐색
   • 연결된 육지를 하나의 섬으로 묶고 고유 번호 부여
2. 가장자리 육지 판별
   • 상하좌우 중 하나라도 바다와 인접한 육지는 섬의 가장자리
3. 다익스트라로 다리 길이 탐색
   • 시작 섬 번호를 제외한 다른 섬을 만날 떄까지 탐색
   • 다른 섬 최초로 만난 순간의 비용이 해당 경로의 다리 길이
   • nonlocal answer 값 갱신
   • 현재 비용 >= answer면 탐색 중단( 가지치기 )

---

 

🧾 코드

import sys, heapq
from collections import deque

def _main():
    answer = 1000
    fd_key = 2

    def _check_line(h, w):
        for n_h, n_w in ((h + 1, w), (h - 1, w), 
                         (h, w + 1), (h, w - 1)):
            if (0 <= n_h < n) and (0 <= n_w < n) and (map_lst[n_h][n_w] == 0):
                return True
        return False

    def _ds(x, y, u_key):
        nonlocal answer
        visit = [[False] * n for _ in range(n)]
        visit[x][y] = True
        hq = [(0, x, y)]

        while hq: # 다익스트라 알고리즘
            cost, start_x, start_y = heapq.heappop(hq)

            # 중단 조건 : 앞으로 최단 거리가 의미 없는 경우 end..
            if cost >= answer:
                break

            for n_x, n_y in ((start_x + 1, start_y), 
                             (start_x - 1, start_y),
                             (start_x, start_y + 1), 
                             (start_x, start_y - 1)):
                if (0 <= n_x < n) and (0 <= n_y < n) and (not visit[n_x][n_y]) and (map_lst[n_x][n_y] != u_key):
                    if map_lst[n_x][n_y] == 0:
                        visit[n_x][n_y] = True
                        heapq.heappush(hq, (cost + 1, n_x, n_y))
                    else: # 중단 조건: 엇! 다른 육지 발견..
                        answer = cost
                        break

    for i in range(n):
        for j in range(n):
            if map_lst[i][j] == 1:
                    
                map_lst[i][j] = fd_key
                queue = deque([(i, j)])

                while queue:
                    x, y = queue.popleft()

                    for n_x, n_y in ((x + 1, y), (x - 1, y), 
                                     (x, y + 1), (x, y - 1)):
                        if (0 <= n_x < n) and (0 <= n_y < n) and (map_lst[n_x][n_y] == 1):
                            map_lst[n_x][n_y] = fd_key
                            queue.append((n_x, n_y))
                fd_key += 1         

    # 거리체크
    for i in range(n):
        for j in range(n):
            # 육지 and 가장자리
            if map_lst[i][j] != 0 and _check_line(i, j):
                _ds(i, j, map_lst[i][j])

    return answer


n = int(sys.stdin.readline().rstrip())
map_lst = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

print(_main())

---

 

⏱️ 시간 복잡도

_ds(x, y, u_key) : 다익스트라 알고리즘 ( 이차형 로그 )

해당 알고리즘 시간 복잡도 : 이차형 로그 시간 복잡도 ( O(n**2 log n) )

---