코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.

• IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
• 상세 설명 - 수원대학교(대학일자리 플러스센터)

---

BFS - 미로의 최단거리 통로

앞서 공부한 BFS(너비 우선 탐색)을 사용해 미로의 최단거리 통로 문제를 풀어보겠다.

---

문제

7*7 격자판 미로를 탈출하는 최단경로의 길이를 구하려고 합니다. 경로의 길이는 출발점에서 도착점까지 가는데 이동한 횟수를 의미한다. 출발점은 격자의 (0, 0) 좌표이고, 탈출 도착점은 (6, 6)좌표이다. 격자판의 1은 벽이고, 0은 도로이다.
격자판의 움직임은 상하좌우로만 움직입니다. 미로가 다음과 같다면

위와 같은 경로가 최단 경로의 길이는 12이다.
매개변수 board에 7*7 격자판 미로 정보가 주어지면 도착점에 도달하는 최단경로의 길이를 구하세요. 도착할 수 없으면 -1를 반환합니다.

---

입출력 예

board	answer
[[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]]	12
[[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, 1, 1, 1], [1, 1, 0, 1, 0, 0, 0], [1, 0, 0, 0, 1, 0, 0], [1, 0, 1, 0, 1, 0, 0]]	-1
[[0, 0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 1, 0], [0, 0, 0, 1, 0, 0, 0], [1, 1, 0, 1, 0, 1, 1], [1, 1, 0, 0, 0, 1, 0], [1, 0, 0, 0, 1, 0, 0], [1, 0, 1, 0, 0, 0, 0]]	18

---

코드

from collections import deque, defaultdict
def BFS(board):

    Q = deque()
    dist = [[0]*7 for _ in range(7)]
    dr = [-1, 0, 1, 0]
    dc = [0, 1, 0, -1]

    # 현재 위치
    Q.append([0, 0])
    board[0][0] = 1
    L = 0

    while Q:
        n = len(Q)                  # 현재 레벨의 원소 개수
        for _ in range(n):
            r, c = Q.popleft()      # 현재 레벨의 원소를 하나 뺌
            for i in range(4):      # 모든 방향 탐색
                nr = r + dr[i]
                nc = c + dc[i]
                # 격자판을 나가지 않고, 이미 가지 않거나, 도로인 경우에만 
                if 0 <= nr < 7 and 0 <= nc < 7 and board[nr][nc] == 0:
                    Q.append([nr, nc])
                    # 이미 지나갔으니 표시
                    board[nr][nc] = 1
                    # 횟수 표시
                    dist[nr][nc] = L + 1
        L += 1
    # 못 갔을 경우 어차피 0으로 초기화 되어있기 때문에
    if dist[6][6]:
        return dist[6][6]
    else:
        return -1

def solution(board):
    answer = BFS(board)
    return answer
    

---

풀이

먼저 board의 크기와 같은 해당 좌표까지의 최소 거리를 표시할 2차원 배열 dist를 만든다.
이 2차원 배열을 0으로 다 초기화한 후 만약 탐색이 끝났을 때도 탈출 좌표의 값이 0이면 탈출하지 못한 것을 의미하므로, -1을 리턴해준다.

또한, 이미 지나온 도로(0)는 중복으로 이동하지 않도록 벽(1)으로 바꿔준다.

또, dr, dc 방향 배열을 만들어 움직일때마다 격자판을 나가지 않는지, 이미 지나온 도로가 아니면서, 벽이 아닌지를 확인해 자식 노드를 계속 생성해나간다.

따라서 갈 수 있는 도로를 모두 탐색한 후 탈출 좌표의 최소 거리를 나타내는 dist[6][6]의 값이 0이면 탈출하지 못 한 것이므로 return -1을 하고 탈출에 성공했다면 return dist[6][6]을 해 탈출 좌표까지의 최소 거리를 출력해준다.