064 - 미로의 최단거리 통로(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
#import sys
#sys.stdin = open('in.txt', 'rt')


if __name__ == '__main__':
    a = [list(map(int, input().split())) for _ in range(7)]

    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    start = [0, 0]
    # 2부터 시작해서 나중에 2를 빼주면 된다. 길(0)과 벽(1)을 구분하기위해서 함
    a[0][0] = 2
    dq = deque()
    dq.append((0, 0))
    while dq:
        tmp = dq.popleft()
        x1 = tmp[0]
        y1 = tmp[1]
        for i in range(4):
            x = x1+dx[i]
            y = y1+dy[i]
            if 0 <= x <= 6 and 0 <= y <= 6 and a[x][y] == 0:
                a[x][y] = a[x1][y1]+1
                dq.append((x, y))

    # print(dq)
    # for x in a:
    #     print(x)
    if a[6][6] == 0 or a[6][6] == 1:
        print(-1)
    else:
        print(a[6][6]-2)