[ BOJ / 파이썬 ] 2178.미로 탐색

BFS

BFS문제 중 거리 측정 유형이다.

BFS문제의 가장 전형적인 유형이기도 하고, 개인적으로 주구장창 풀었던 스타일이라 술술 써내려갔다.

 

문제 ( 링크 )

 

 

기본적인 BFS는 방문 여부를 담을 배열을 따로 두지만, 해당 문제에서 밟아야할 공간이 1이므로 1 이상인 경우는 방문했다고 여기며 그 자리에 현재까지의 최단거리를 바로 대체해 넣는 방식으로 코드를 작성했다. 

 

제출 1. 통과

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

def main():
  n, m = map(int, input().split())
  board = [list(map(int, list(input().strip()))) for _ in range(n)]

  dx = [-1, 1, 0, 0]
  dy = [0, 0, -1, 1]
  q = deque([(0, 0)])
  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 < m and board[nx][ny] == 1:
        q.append((nx, ny))
        board[nx][ny] = board[x][y] + 1
        
  print(board[n-1][m-1])
if __name__ == '__main__':
  main()