[코테] BFS - 미로 탈출[프로그래머스]

문제

출처: 프로그래머스 - 미로 탈출

풀이

BFS 최단거리 탐색 문제다.
1. 시작지점에서 출발하여 반드시 레버를 당긴 후에 탈출 지점으로 이동해야 한다. 그러므로 출발 -> 레버, 레버 -> 탈출 경로로 2번의 BFS를 시행하여 두 번의 이동 경로의 합을 구하면 된다.
2. 2번의 BFS를 시행할 때, BFS 함수를 만들어서 같은 코드를 2번 쓰지 않도록 하자.
3. BFS 함수를 생성할 때, 시작지점과 도착지점, maps를 각각 던져 탐색하도록 만든다. 만약 2번의 BFS를 시행하여 1번이라도 -1이 반환되면 탈출할 수 없으므로 -1을 반환하고 아니라면 각각 시행한 후 그 거리를 합한 것을 반환하면 된다.
4. BFS 함수는, 먼저 상하좌우 탐색할 수 있는 좌표를 생성하고 재방문하지 않도록 체크할 수 있는 체크 배열을 생성한다. 그리고 큐를 이용하여 가까운 좌표(먼저 들어온 좌표)부터 꺼내어 탐색할 수 있도록 큐 자료구조를 생성한다. 자세한 것은 코드를 보자.

코드

from collections import deque

def BFS(s, e, maps):
    n = len(maps) # 행 - y
    m = len(maps[0]) # 열 - x
    dx = [0, 1, 0, -1] # 상하좌우 탐색
    dy = [-1, 0, 1, 0]
    ch = [[0] * m for _ in range(n)] # 체크 배열: 0은 방문하지 않은 지점, 1은 방문한 지점
    dQ = deque()

    for i in range(n): # 출발지점 좌표 탐색
        for j in range(m):
            if maps[i][j] == s:
                dQ.append((i, j, 0)) # y좌표, x좌표, 거리
                ch[i][j] = 1 # 시작지점 방문 처리

    while dQ:
        y, x, dis = dQ.popleft() # 가까운 곳부터 탐색

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # 전체 maps의 좌표를 벗어나지 않도록, 'X'가 아닌 곳만 방문할 수 있도록, 방문하지 않은 곳만 방문하도록
            if 0 <= nx < m and 0 <= ny < n and maps[ny][nx] != 'X' and ch[ny][nx] == 0:
                dQ.append((ny, nx, dis + 1)) # 방문이 가능하다면 큐에 넣어주고 거리를 +1
                ch[ny][nx] = 1 # 재방문하지 않도록
                if maps[ny][nx] == e: # 현재 방문한 지점이 도착지점이라면 바로 탈출하여 불필요한 연산을 하지 않도록 한다.
                	return dis + 1

    return -1 # 이 지점까지 왔다는 것은 도착지점을 방문하지 못했다는 것이기에 탈출을 할 수 없다.


def solution(maps):
	# 두 번의 BFS 실행
    res1 = BFS('S', 'L', maps)
    res2 = BFS('L', 'E', maps)
    
    if res1 == -1 or res2 == -1: # 하나라도 -1이 있다면 탈출을 하지 못하므로 -1 반환
        return -1
    else:
        return res1 + res2 # 두 번의 시행 거리 합을 반환