[백준] 2665번 미로만들기 파이썬 코드

코드

# 가중치가 0, 1만 존재하고 최단거리를 찾는 문제
# 0-1 bfs을 이용하면 쉽게 해결할 수 있다.

import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
graph = [list(input().rstrip()) for _ in range(n)]
visited = [[0]*n for _ in range(n)] # 방문기록 리스트

dx, dy = [1,-1,0,0], [0,0,1,-1] # 이동할 수 있는 경우의 수
def bfs(start,end):
  queue = deque([(start,end)])
  visited[start][end] = 1 # 처음 시작점 방문 기록
  while queue:
    x,y = queue.popleft()
    if x == (n-1) and y == (n-1): return visited[x][y] # 끝점에 도달하면 함수 종료
    for i in range(4):
      nx = x+dx[i]
      ny = y+dy[i]
      if 0<=nx<n and 0<=ny<n and not visited[nx][ny]: # 그래프 범위 안에 있고 방문하지 않은 경우 
        if graph[nx][ny] == '0': # 검은 방인 경우
          queue.append((nx,ny)) # 가중치가 1이므로 뒤에 추가
          visited[nx][ny] = visited[x][y] + 1 # 개수 증가
        else: # 흰 방인 경우
          visited[nx][ny] = visited[x][y] # 개수는 이전과 그대로
          queue.appendleft((nx,ny)) # 가중치가 0이므로 앞에 추가
          
print(bfs(0,0)-1) # 처음에 1개 추가해주었으니 1개 빼준 값을 출력