[ BOJ / 파이썬 ] 2146 다리 만들기

/  제출 1  /  (소요 시간: 1시간)

import sys
input = sys.stdin.readline
from collections import deque
from copy import deepcopy

n = int(input())

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
board = [list(map(int, input().split())) for _ in range(n)]
teamMin = {}
def getCandidateBridge():
  teamNum = 10000 + 1
  q = deque([])
  candidate = []
  for i in range(n):
    for j in range(n):
      if board[i][j] == 1:
        q.append((i, j))
        board[i][j] = teamNum
        teamMin[teamNum] = teamNum
        while q:
          x, y = q.popleft()
          faceSea = False
          for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
    
            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 1:
              q.append((nx, ny))
              board[nx][ny] = teamNum

            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 0:
              faceSea = True
          if faceSea:
            candidate.append((x, y))
        teamNum += 1
  return candidate


bridgeOptions = getCandidateBridge()

for option in bridgeOptions:
  visited = [[0] * n for _ in range(n)]
  i, j = option
  q = deque([(i, j)]) 
  visited[i][j] = 1
  myTeamMin = teamMin[board[i][j]]
  
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < n and 0 <= ny < n:
        if board[nx][ny] == 0 and not visited[nx][ny]:
          visited[nx][ny] = visited[x][y]+1
          q.append((nx, ny))
        if not visited[nx][ny] and board[nx][ny] != 0 and board[nx][ny] != board[x][y]:
          myTeamMin = min(myTeamMin, visited[x][y]+1)

        if visited[nx][ny] > myTeamMin:
          break

  
  teamMin[board[i][j]] = myTeamMin

print(min(teamMin.values()))

7%에서 터졌습니다.

 

틀린 것 알지만 기록용으로 제출했는데 일부 맞긴하나봅니다.

 

중간에 꼬여 버려서 원하는대로 결과값이 안 나왔습니다. 시간이 많이 소요되어서 일단 스탑하고 풀이 보고 다시 꼬인 부분 정리하겠습니다.

 

로직은 맞는데 구현하면서 일을 꼬아버린 부분이 좀 있는 것 같습니다.

 

https://coarmok.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%ACpython-%EB%B0%B1%EC%A4%80-2146%EB%B2%88-%EB%8B%A4%EB%A6%AC-%EB%A7%8C%EB%93%A4%EA%B8%B0

[파이썬python] 백준 2146번 - 다리 만들기