파이썬 알고리즘-62 (DFS/BFS 활용) 미로의 최단거리 통로

62.미로의 최단거리 통로(BFS 활용)
7*7 격자판 미로를 탈출하는 최단경로의 경로수를 출력하는 프로그램을 작성하세요. 경로수는
출발점에서 도착점까지 가는데 이동한 횟수를 의미한다. 출발점은 격자의 (1, 1) 좌표이고, 탈
출 도착점은 (7, 7)좌표이다. 격자판의 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 도착
위와 같은 경로가 최단 경로이며 경로수는 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

dx=[0,1,0,-1]
dy=[-1,0,1,0]
lst=[]
for _ in range(7):
    tmp=list(map(int,input().split()))
    tmp.insert(0,1)
    tmp.append(1)
    lst.append(tmp)
lst.insert(0,[1]*9)
lst.append([1]*9)

ch=[[0]*9 for i in range(9)]
ch[1][1]=1
dq=deque()
dq.append((1,1))
dis=[[0]*9 for _ in range(9)]
while True:
    if tmp==(7,7):
        break
    size=len(dq)
    for i in range(size):
        tmp=dq.popleft()
        for j in range(4):
            x=tmp[0]+dx[j]
            y=tmp[1]+dy[j]
            if ch[x][y]==0 and lst[x][y]==0:
                ch[x][y]=1
                dq.append((x,y))
                dis[x][y]=dis[x-dx[j]][y-dy[j]]+1

print(dis[7][7])

출발점이 문제상으로는 (1,1)인데 인덱스에서는 (0,0)이므로 이를 맞추기 위해 주변을 1로 감쌌다. 한 번 지나간 곳은 다시 돌아가지 않게 한답시고 ch까지 만들었는데 굳이 그럴 필요도 없었다. 그리고 종료하는 시점을 잘못잡아서 pop되는게 마지막 점일 때만 break되도록 했는데, 이렇게 하면 도달하지 못했을 때 빠져나올 방법이 없게 된다.

풀이

from collections import deque

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])

반성점

• 거의 답을 보고 한거나 마찬가지인데도 틀림
• 쓸데없는 코드가 많음

배운 것

• 미로의 최단거리를 구할 때는 다시 돌아가지 않기 위해 지나온 곳에 1을 하는 것으로 충분하다.
• 거리를 구할 때는 지나온 좌표마다 거리를 표시해줘야 마지막에 최단거리가 나온다.