[programmers/py] 미로 탈출

미로 탈출

https://school.programmers.co.kr/learn/courses/30/lessons/159993

문제 설명

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다.

각 칸은 S, E, L, O, X로 구성되어 있으며, X는 지나갈 수 없는 칸입니다.

S->E로 갈 때, 중간에 꼭 L을 들려 E에 도착하려 합니다.
각 칸을 이동할 때 1의 시간이 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

풀이

BFS 문제

우선 문제를 보고 S->L, L->S 두 개의 시간을 각각 구해서 답을 구해야 합니다.
중요한 건 S->L로 가는 도중 E를 지나칠 경우를 생각해 visited 배열을 초기화 해야합니다.

from collections import deque

def bfs(s, e, maps):
    
    # 시작에서 L, L에서 E까지 각각 도달할 때 visited가 초기화 되어야 함
    n = len(maps) # 세로
    m = len(maps[0]) # 가로
    visited = [[False]*m for _ in range(n)]
    
    dq = deque()
    
    # 동 서 남 북
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    findStart = False
    
    for i in range(n):
        for j in range(m):
            if maps[i][j] == s:
                dq.append((i,j,0))
                visited[i][j] = True
                findStart = True
                break
        if findStart == True :
            break
                
    while dq:
        x, y, time = dq.popleft()
        
        if maps[x][y] == e:
            return time
        
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]
            
            # 다음 칸 갈 수 있다면
            if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] != "X":
                if not visited[nx][ny]:
                    dq.append((nx,ny,time+1))
                    visited[nx][ny] = True
    return -1

def solution(maps):
    answer = 0
    
    toL = bfs("S", "L", maps)
    
    if toL == -1:
        return -1
    
    toE = bfs("L", "E", maps)
    
    if toE == -1:
        return 0-1
    
    return toL+toE