9.미로의 최단거리 통로(BFS)

미로의 최단거리 통로(BFS) -문제는 생략

 

문제풀이

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)]
board[0][0] =1  #이미 방문
dis=[[0]*7 for _ in range(7)] 
dis[0][0] = 0   #0으로 세팅한다.
Q=deque()
Q.append((0,0))

                
while Q:
    tmp=Q.popleft()     #tmp에는 튜플 1개만 저장된다 tmp는 현재시점에서의 부모를 의미한다. 
    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:  #x,y는 "next" 좌표를 의미한다. 
            Q.append((x,y))
            board[x][y]=1  #발자국을 남긴다. 
            dis[x][y]=dis[tmp[0]][tmp[1]]+1


if dis[6][6]==0:
    print(-1)
else: 
    print(dis[6][6])

 

Hint

▶이미 방문한 곳은 board[i][j] ==1로 표시해서 흔적을 남긴다.

 

▶다음에 방문할 좌표를 만들기 위한 예비작업으로 9시방향,  12시방향, 3시방향,  6시방향의 리스트를 만든다.

 

▶큐에서 popleft()를 했을 때 tmp는 현재시점에서의 부모를 의미한다. 

 

▶tmp가 큐에서 pop되었을 때, 4개의 자식(branch)가 생긴다.

 

▶dis은 step의 수를 기록하는 도구이며, 부모좌표에서 한칸이동할때마다 step을 +1증가시킨다. 

 

▶tmp[0]과 tmp[1]은 각각 부모좌표의  x, y를 의미한다. 

 

▶dis[ tmp[0] ] [tmp[1] ] 은 dis 배열에서의  부모좌표를 의미하며, 

 

▶dis[x][y]=dis[tmp[0]][tmp[1]]+1은 next 좌표 = 부모좌표 +1을 의미한다.