66)미로의 최단거리(BFS)

문제

7*7 격자판 미로를 탈출하는 최단경로의 경로수를 출력하는 프로그램을 작성하기

 

조건

경로수는 출발점에서 도착점까지 가는데 이동한 횟수를 의미한다.

 

출발점은 격자의 (1, 1) 좌표이고, 탈 출 도착점은 (7, 7)좌표이다.

 

격자판의 1은 벽이고, 0은 도로이다.

 

격자판의 움직임은 상하좌우로만 움직인다.

 

미로가 다음과 같다면

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

 

제한사항

7*7 격자판의 정보가 주어집니다.

 

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

 

문제풀이

from collections import deque

dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
a=[list(map(int, input().split())) for _ in range(7)]
dis=[[0]*7 for _ in range(7)]
dQ=deque()
dQ.append((0, 0))
a[0][0]=1

while dQ:
  tmp=dQ.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 a[x][y]==0:
      a[x][y]=1
      dis[x][y]=dis[tmp[0]][tmp[1]]+1
      dQ.append((x, y))

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