[BOJ 2178] 미로 탐색

Breadth First Search

BOJ 2178번 미로 탐색

문제

구조화

• 2D BFS 문제
• 배열의 세로 N, 배열의 가로 M 정의
• N만큼 M크기의 리스트 입력
• N by m 크기의 좌표 생성
• 1,1의 위치에서 목표지점 N,M까지의 몇 칸을 이동하는지 구하는 문제
  • 이동 거리가 아니기에 초기 자신의 위치도 포함하여 계산
• 2D 형태의 이동
  • 오른쪽 = [1,0]
  • 왼쪽 = [-1,0]
  • 위쪽 = [0,1]
  • 아래쪽 = [0,-1]
• 위의 Rule에 따라 N,M까지의 최소 거리 출력
• 탐색하지 않아도 될 Condition
  • 이동 후의 좌표가 0일 경우
  • 이동 후의 좌표가 N,M을 벗어난 경우
  • 이동 후의 좌표가 음수가 되어버릴 경우
• Python의 인덱스는 0부터 시작하므로, 0,0 -> n-1, m-1로 탐색

예제 시각화

해답

from collections import deque
n, m = map(int,input().split())
board=[]
for i in range(n):
    board.append(list(map(int,input())))
# 이동량
dx = [-1,1,0,0]
dy = [0,0,-1,1]
arr = deque()
arr.append([0,0])
while arr :
  # 현재 위치
  px, py = arr.popleft()
  # 좌표 이동
  for i in range(len(dx)):
    nx = px+dx[i]
    ny = py+dy[i]
    # board를 벗어나면 continue
    if nx>n-1 or ny>m-1 or nx<0 or ny<0 :
        continue
    # 이동 가능한 좌표라면
    if board[nx][ny]==1:
        # target 좌표로 선정
        arr.append((nx,ny))
        # 좌표 값의 값을 가중하며 거리 계산
        board[nx][ny] = board[px][py]+1 # 직전 노드+1
# 가중된 거리에 따라 마지막 좌표 return
print(board[n-1][m-1])