[Python] 프로그래머스 - 미로 탈출

프로그래머스 미로 탈출 문제는 출발점에서 레버를 당기고 출구로 나가기까지의 최단거리를 구하는 문제다. 난이도는 레벨2이며 BFS를 통해 해결할 수 있다.

 

프로그래머스 - 미로 탈출 문제 정보

알고리즘 분류

- Graph - BFS

난이도

- level 2

 

문제 요약

• HxW 크기의 격자가 주어진다.
  • S: 시작 지점, E: 출구, L: 레버, O: 통로, X: 벽
• 출구로 나가기 위해서는 반드시 레버를 동작시켜야 한다.
• 출구로 나가기위한 최단 이동 거리를 구하라.

 

문제 풀이 과정

• 가중치가 없고 단순히 최단거리를 구하는 문제이므로 BFS를 사용한다.
• 시작점~레버까지의 최단 거리 + 레버~출구까지의 최단거리

코드

import collections


# 같은 maps 배열을 여러번 사용하기 위해 방문한 곳을 표시하는 mark 파라미터를 같이 받는다.
def bfs(start, dest, maps, mark):
    H, W = len(maps), len(maps[0])
    dr, dc = [1,-1,0,0], [0,0,1,-1]
    
    start_r, start_c = start
    queue = collections.deque()
    queue.append((start_r, start_c, 0))
    
    while queue:
        here_r, here_c, here_dist = queue.popleft()
        
        if (here_r, here_c) == dest:
            return here_dist
        
        if maps[here_r][here_c] != 'X' and maps[here_r][here_c] != mark:
            maps[here_r][here_c] = mark
            for i in range(4):
                next_r, next_c = here_r + dr[i], here_c + dc[i]
                if 0 <= next_r < H and 0 <= next_c < W:
                    queue.append((next_r, next_c, here_dist + 1))
    
    return -1
    

def solution(maps):
		# maps를 visited 배열로 사용하기 위해 각 row를 char array로 변환한다.
    maps = [[ s for s in row] for row in maps]
    H, W = len(maps), len(maps[0])
    start, lever, exit = (0,0), (0,0), (0,0)
    for r, row in enumerate(maps):
        for c, s in enumerate(row):
            if s == 'S':
                start = (r, c)
            if s == 'L':
                lever = (r, c)
            if s == 'E':
                exit = (r, c)
            
    to_lever = bfs(start, lever, maps, 'V1')
    if to_lever == -1:
        return -1
    to_exit = bfs(lever, exit, maps, 'V2')
    
    return to_lever + to_exit if to_exit != -1 else -1

• 시간복잡도: O(HW) (정점 개수: HW, 간선 개수: HW4 → O(5HW) = O(H*W))
• 공간복잡도: 큐 사용 공간 O(H*W)