📗 미로 탈출

프로그래머스

from collections import deque

def solution(maps):
    n, m = len(maps), len(maps[0])
    start, end, l_point = None, None, None
    
    for i in range(n):
        for j in range(m):
            if maps[i][j] == 'S':
                start = (i, j)
            elif maps[i][j] == 'L':
                l_point = (i, j)
            elif maps[i][j] == 'E':
                end = (i, j)
    
    def bfs(start, end):
        queue = deque([(start[0], start[1], 0)])
        visited = set([(start[0], start[1])])
        
        while queue:
            x, y, dist = queue.popleft()
            
            if (x, y) == end:
                return dist
            
            for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < m and maps[nx][ny] != 'X' and (nx, ny) not in visited:
                    queue.append((nx, ny, dist + 1))
                    visited.add((nx, ny))
                    
        return -1
    
    l_dist = bfs(start, l_point)
    end_dist = bfs(l_point, end)
    
    return -1 if l_dist == -1 or end_dist == -1 else l_dist + end_dist

• bfs를 이용하여 미로에서 출구를 찾아가는 전형적인 문제였습니다. 

왜 이렇게 풀었을까?

• bfs에 좌표 값을 넘겨주어 출발 지점에서부터 목표 지점까지의 최단 거리를 계산하게끔 구현하였습니다.
• 좌표 값을 넘겨주는 방식으로 미로를 탐색하기 때문에 'S', 'L', 'E' 포인트인 시작, 레버, 출구 포인트의 좌표를 먼저 추출하였습니다.
• 기존에 저는 dx, dy를 다른 변수로 두어 for문에 적용했었는데, for문 범위 자체에 이 dx, dy를 두게 되면서 조금은 간단하게 구현이 된 느낌입니다.
• 이번 문제에서는 다른 문제들과는 달리 시작 지점에서 반드시 레버가 있는 곳에 들렀어야 했기에 최단 거리를 나누어 계산을 해주면 쉽게 풀어낼 수 있습니다.
• 시작 지점에서부터 레버까지, 레버에서부터 출구 지점까지 나누어 계산을 하였고, 두 경로 중 하나라도 -1이 반환된다면 갈 수 없는 경로이기 때문에 최종적으로 -1을 반환하였습니다.