Algorithm - 미로의 최단거리 통로(BFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[미로의 최단거리 통로(BFS)]

 

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

 

단, 경로의 수는 출발점에서 도착점까지 가는데 이동한 횟수를 의미하며 출발점은 격자의 (1, 1) 좌표이고 탈출 도착점은 (7, 7) 좌표이다. 또한, 격자판의 1은 벽이고 0은 도로이다. 

참고로, 격자판의 움직임은 상하좌우로만 움직이며 미로가 아래와 같다면 다음의 경로가 최단경로(12)이다.

 

7*7 격자판

 

*입력 설명

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

 

*출력 설명

첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다.

단, 도착할 수 없는 경우에는 -1을 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
from collections import deque
sys.stdin = open('AA/input_64.txt', 'rt')

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])
    
# 출력 : 12

 

input_64.txt(입력)

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. 최단거리의 문제는 BFS(넓이우선탐색)을 사용하는 것이 효과적이다.
2. BFS 탐색에서는 큐 자료구조를 활용한다.
3. 큐 자료구조에는 튜플 형태로 격자판의 좌표가 저장된다.
4. 상하좌우 탐색이므로 for문의 실행횟수는 4이다.
5. board[x][y] == 0은 지나갈 수 있는 길을 의미하고, board[x][y] == 1은 벽을 의미한다.
6. 이미 지나간 길에 1을 입력해줘야만 최소 경로를 탐색할 수 있다. (경로의 중복 고려 X)
7. board[0][0] = 1 코드는 경로 탐색의 시작점이 (0, 0)이라는 의미이다.
8. board[6][6] 코드는 경로 탐색의 도착점이 (6, 6)이라는 의미이다.