[인프런] 미로의 최단거리 통로

---

문제설명

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

 

 

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

입력조건

• 7 by 7 격자판의 정보가 주어진다.

출력조건

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

사고과정

• 최솟값을 출력하라고 한 것에서 BFS를 캐치했어야 한다. 
• 전형적인 BFS 문제로, 방문테이블을 새로 정의하여 방문하는 노드를 테이블에 체크해주어야 한다.
• 도달할 수 없는 경우를 처리하기 위해 while ~ else 구문을 사용했다.(while 조건문이 위배되면 else 구문을 실행한다!)

풀이

visited = [[0] * 7 for _ in range(7)]
arr = [list(map(int, input().split())) for _ in range(7)]
# 이동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 출발 좌표
x, y = 0, 0
visited[x][y] = 1
arr[x][y] = 0
queue = deque([(x, y)])
# while ~ else 구문도 가능: while 조건식 거짓으로 되서 while 안에 구문 동작안하면 else 수행됨! for ~ else와 동일!
while queue:
    x, y = queue.popleft()
    if x == 6 and y == 6:
        print(arr[x][y])
        break
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < 7 and 0 <= ny < 7: # 맵 안에있을 경우
            if arr[nx][ny] == 0 and visited[nx][ny] == 0: # 도로이면서 방문하지 않은 곳일 경우
                visited[nx][ny] = 1
                arr[nx][ny] = arr[x][y] + 1
                queue.append((nx, ny))
else:
    print(-1)