[BOJ] 2146 다리 만들기 Python 풀이

2146번: 다리 만들기

아이디어에 대한 힌트는 인터넷을 참고하였다.

처음 풀어보는 유형이다.

아래 문제는 BFS를 2번 적용하여 탐색하였다.

우선 "섬" 인 곳은 라벨링을 하였고 (2~n) 여기서 섬을 찾을때 첫번쨰 BFS를 이용하였다.

 

두번쨰로 섬과 섬을 잇는 바다를 탐색할 때인데, BFS로 탐색 후 새로운 섬을 만나게 되면 이전의 result값과 비교한다.

result와 비교하여 더 작은 값을 result에 넣은 후 마지막에 result를 출력하면 가장 짧은 다리의 거리가 나온다.

 

사실 이번 문제까지만 풀고 그래프 졸업하려 했는데,, 조금만 더 풀어보기로 결정했다..

from collections import deque
n = int(input())
result = 999
graph = [list(map(int, input().split())) for _ in range(n)]

continent_map = [[0 for _ in range(n)] for __ in range(n)]

def getContinent(x, y, mapped):
  visited = [[0 for _ in range(n)] for __ in range(n)]
  q = deque()
  q.append([x, y])
  visited[x][y] = 1
  graph[x][y] = mapped
  dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
  
  while q:
    cx, cy = q.popleft()
    for i in range(4):
      nx = dx[i] + cx
      ny = dy[i] + cy

      if 0 <= nx < n and 0 <= ny < n:  # 범위안에 있을때
        if visited[nx][ny] == 0 and graph[nx][ny] != 0:
          graph[nx][ny] = mapped
          visited[nx][ny] = 1
          q.append([nx, ny])

m = 2
for i in range(n):
  for j in range(n):
    if graph[i][j] == 1:

      getContinent(i, j, m)  # 2부터 시작하는 숫자로 매핑
      m += 1


def buildBriedge(nn):
  global result
  visited = [[-1 for _ in range(n)] for __ in range(n)]
  q = deque()
  dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]

  for i in range(n):
    for j in range(n):
      if graph[i][j] == nn:
        q.append([i, j])
        visited[i][j] = 0



  while q:
    cx, cy= q.popleft()
    for i in range(4):
      nx = dx[i] + cx
      ny = dy[i] + cy
      if 0 <= nx < n and 0 <= ny < n:
        if graph[nx][ny] > 0 and graph[nx][ny] != nn:
          result = min(result, visited[cx][cy])
          return

        if graph[nx][ny] == 0 and visited[nx][ny] == -1:
          visited[nx][ny] = visited[cx][cy] + 1
          q.append([nx, ny])



for i in range(2, m):
  buildBriedge(i)
  
print(result)