[BFS 활용] - 미로의 최단거리 통로

 

미로의 최단거리 통로

 

7*7 격자판 미로를 탈출하는 최단경로의 경로수를 출력하는 프로그램을 작성하세요. 경로수는 출발점에서 도착점까지 가는데 이동한 횟수를 의미한다. 출발점은 격자의 (1, 1) 좌표이고, 탈 출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 도로이다.
격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

위와 같은 경로가 최단 경로이며 경로수는 12이다.

 

▣ 입력설명
7*7 격자판의 정보가 주어집니다.

▣ 출력설명
첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 도착할 수 없으면 -1를 출력한다.

 

▣ 입력예제 1

0 0 0 0 0 0 0

0 1 1 1 1 1 0

0 0 0 1 0 0 0

1 1 0 1 0 1 1 

1 1 0 1 0 0 0

1 0 0 0 1 0 0

1 0 1 0 0 0 0

▣ 출력예제 1

12

 

 

나의 코드

from collections import deque

arr=[list(map(int,input().split())) for _ in range(7) ]
# ch=[[0]*7 for _ in range(7)]

dq=deque()

dq.append((0,0))

dx=[-1,0,1,0]
dy=[0,1,0,-1]
arr[0][0]=1
while dq:

    for i in range(len(dq)):
        x,y=dq.popleft()
        if x==6 and y==6:
            print(arr[6][6]-1)
        for k in range(4):
            nx=x+dx[k]
            ny=y+dy[k]
            if 0<=nx<7 and 0<= ny <7 and arr[nx][ny]==0:
                dq.append((nx,ny))
                arr[nx][ny]=arr[x][y]+1

방향 벡터를 사용하며 BFS 탐색을 진행하며 체크리스트 겸 거리 기록겸 arr을 사용

 

import sys
from collections import deque
sys.stdin=open("input.txt", "r")
dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
board=[list(map(int, input().split())) for _ in range(7)]
dis=[[0]*7 for _ in range(7)]
Q=deque()
Q.append((0, 0))
board[0][0]=1
while Q:
    tmp=Q.popleft()
    for i in range(4):
        x=tmp[0]+dx[i]
        y=tmp[1]+dy[i]
        if 0<=x<=6 and 0<=y<=6 and board[x][y]==0:
            board[x][y]=1
            dis[x][y]=dis[tmp[0]][tmp[1]]+1
            Q.append((x, y))
if dis[6][6]==0:
    print(-1)
else:
    print(dis[6][6])

 

정답 코드는 문제 풀이의 편이를 위해 dis라는 새로운 배열로 거리를 저장하였지만 나의 코드처럼 굳이 필요는 없다.