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

와아.. BFS 이제 뚫렸나보다.. 행복해.. 재밌어..

 

풀이 소요 시간 30분. 통과

# 2:40
from collections import deque
n = int(input())

def make_continent(i, j, board, visited, index):
  n = len(board)
  dx = [-1, 0, 1, 0]
  dy = [0, 1, 0, -1]
  q = deque([(i, j)])
  visited[i][j] = True
  board[i][j] = index
  while q:
    x, y = q.popleft()
    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 and not visited[nx][ny]:
        visited[nx][ny] = True
        board[nx][ny] = index
        q.append((nx, ny))

  return [board, visited]
board = [list(map(int, input().split())) for _ in range(n)]
index = 1
visited = [[False] * n for _ in range(n)]
result = int(1e9)
for i in range(n):
  for j in range(n):
    if board[i][j] == 1 and not visited[i][j]:
      board, visited = make_continent(i, j, board, visited, index)
      index += 1


def make_bridge_from(i, j, board):
  q = deque([(i, j)])
  from_continent = board[i][j]
  visited = [[0] * n for _ in range(n)]
  dx = [-1, 0, 1, 0]
  dy = [0, -1, 0, 1]
  while q:
    x, y = q.popleft()
    for k in range(4):
      nx = x + dx[k]
      ny = y + dy[k]
      if 0 <= nx < n and 0 <= ny < n:
        if board[nx][ny] != 0 and board[nx][ny] != from_continent:
          return visited[x][y] 
        elif board[nx][ny] == 0 and not visited[nx][ny]:
          visited[nx][ny] = visited[x][y] + 1
          q.append((nx, ny))
  return 0
dist_board = [[0] * n for _ in range(n)]
for i in range(n):
  for j in range(n):
    if board[i][j] != 0:
      shortest_dist = make_bridge_from(i, j, board)
      dist_board[i][j] = shortest_dist
      if shortest_dist:
        result = min(result, shortest_dist)
print(result)

 

 

 

다른 분 코드인데 이 분은 내 풀이 실행 시간 1/3 밖에 안 걸린다.. 😥

import sys
from collections import deque

sys.setrecursionlimit = 100000
input = sys.stdin.readline

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
            
def numbering(i, j, num):
    que = deque()
    que.append((i, j))
    graph[i][j] = num
    while que:
        x, y = que.popleft()
        for n in range(4):
            xx = x + dx[n]
            yy = y + dy[n]
            if 0 <= xx < N and 0 <= yy < N and graph[xx][yy] == 1:
                graph[xx][yy] = num
                que.append((xx, yy))


def BFS(i, j, num):
    global answer
    que = deque()
    que.append((i, j, 1))
    visited[i][j] = 1
    while que:
        x, y, length = que.popleft()
        if length >= answer:
            return answer
        for n in range(4):
            xx = x + dx[n]
            yy = y + dy[n]
            if 0 <= xx < N and 0 <= yy < N and visited[xx][yy] > length + 1:
                if graph[xx][yy] == 0:
                    visited[xx][yy] = length+1
                    que.append((xx, yy, length+1))
                elif graph[xx][yy] != num:
                    return min(length, answer)
    return answer


input = sys.stdin.readline

# input & 변수 초기화
N = int(input())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

MAX_NUM = 2147000000
visited = [[MAX_NUM] * N for _ in range(N)]
answer = MAX_NUM

# 서로 다른 섬 표시 (numbering)
num = 2
for i in range(N):
    for j in range(N):
        if graph[i][j] == 1:
            numbering(i, j, num)
            num += 1

# 다리 탐색 (BFS)
for i in range(N):
    for j in range(N):
        if graph[i][j]:
            for n in range(4):
                ii = i + dx[n]
                jj = j + dy[n]
                if 0 <= ii < N and 0 <= jj < N and not graph[ii][jj] and visited[ii][jj] > 0:
                    answer = BFS(ii, jj, graph[i][j])

print(answer)

 

 

아 .. 그니까 나는 모든 가능성 있는 시작지점에 대해 거리를 구하는데. 사실 결과값인 최소거리를 넘어가면 그 시작지점은 거리 계산을 이어가지 말고 그냥 끊어줘야 쓸데없는 연산을 하지 않을 수 있다. early return! 생각해보기..