[프로그래머스 > Lv2] 미로탈출

프로그래머스

 

1. 문제

최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

 

[입력]

- 미로를 나타내는 문자열 배열 maps

 

[결과]

- 미로를 탈출하는데 필요한 최소 시간 return

(* 만약 탈출할 수 없다면 -1을 return)

 

2. 풀이

간단하게 bfs를 수행하는 별도의 함수를 만들어두고 아래의 두 최소 이동 거리를 계산하였습니다.

1. 시작점 -> 레버
2. 레버 -> 출구

만약 1과 2 중 하나라도 도착하지 못하는 상황이라면 -1을 반환해주고

그렇지 않다면 1 + 2를 반환해주면 됩니다.

 

bfs 메서드는 일반 너비우선탐색 코드와 동일하기 때문에 어려움 없이 구현할 수 있습니다. 

 

3. 코드

Python

dx = [-1,0,1,0]
dy = [0,1,0,-1]
def solution(maps):
    answer = 0
    n, m = len(maps), len(maps[0])
    start_x, start_y = 0,0
    end_x, end_y = 0,0
    level_x, level_y = 0,0
    
    for x in range(n):
        for y in range(m):
            if maps[x][y]=='S':
                start_x,start_y = x,y
            elif maps[x][y]=='L':
                level_x,level_y = x,y
            elif maps[x][y]=='E':
                end_x,end_y = x,y
    
    to_level = bfs(start_x,start_y,level_x,level_y,maps,n,m)
    if to_level == 0: return -1
    to_end = bfs(level_x,level_y,end_x,end_y,maps,n,m)
    if to_end == 0: return -1
    return to_level + to_end

def bfs(
    start_x,start_y,
    end_x, end_y,
    maps, n, m
):
    q = []
    q.append((start_x,start_y, 0))
    visited = [[False] * m for _ in range(n)]
    visited[start_x][start_y] = True
    
    while q:
        x, y, distance = q.pop(0)
        
        if x==end_x and y==end_y:
            return distance
        
        for d in range(4):
            nx, ny = x+dx[d], y+dy[d]
            if 0<=nx<n and 0<=ny<m and maps[nx][ny]!='X' and not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((nx,ny,distance+1))
        
    return 0