[프로그래머스] 미로 탈출 python

문제

프로그래머스

코드

from collections import deque 

def solution(maps):
    maps = [list(_) for _ in maps]
    rows, cols = len(maps), len(maps[0])
    distance = [[-1 for _ in range(cols)] for _ in range(rows)]
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    q = deque()
    
    for i in range(rows):
        for j in range(cols):
            if maps[i][j] == 'L':
                q.append((i, j, 0))
                distance[i][j] = 0
    while q:
        cx, cy, dist = q.popleft()
        
        for dx, dy in d:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < rows and 0 <= ny < cols and maps[nx][ny] != 'X' and distance[nx][ny] == -1:
                distance[nx][ny] = dist + 1
                q.append((nx, ny, dist + 1))
                
    l_dist, e_dist = -1, -1
    for i in range(rows):
        for j in range(cols):
            if maps[i][j] == 'S' and l_dist == -1:
                l_dist = distance[i][j]
            if maps[i][j] == 'E':
                e_dist = distance[i][j]
    
    if l_dist == -1 or e_dist == -1:
        return -1
    else:
        return l_dist + e_dist

풀이

• 시작지점부터 레버까지, 그리고 레버부터 탈출지점까지의 거리를 구해라

1. 입력받은 문자열을 리스트형태로 변환
2. 거리를 입력할 배열 구현
3. 시작지점부터 바로 탈출지점까지 가는게 아닌 중간에 레버를 올려야하므로 레버를 기준으로 시작지점과 탈출지점의 최단거리를 구하면 된다고 생각
   1. bfs를 활용해 레버의 위치인 ‘L’부터 시작, 전체 미로의 거리를 L을 기준으로 기입
   2. 거리를 입력한 distance 배열에서 시작지점인 S와 탈출지점인 E의 좌표에 대한 거리의 합을 출력
   3. 만약 하나라도 -1인 경우 길이 없는것이므로 -1 출력

특이사항

• 출발 지점부터 레버까지와 레버부터 도착 지점까지의 길이 중복되도 된다길래 어떻게 구현해야할지 생각하다가, 두번의 bfs를 돌리면 되겠다고 생각했다. → 하지만 이렇게 구현할 경우 낭비가 심하다고 생각. → 중간 지점인 레버를 기준으로 거리를 구하면 bfs를 한번만 돌릴 수 있다고 생각 후 구현