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

문제

프로그래머스

 

문제 풀이

• 레버까지 도달하는 데 걸리는 시간 + 레버부터 목적지까지 도달하는 데 걸리는 시간을 해야 하므로 bfs를 두 번 돌려야한다.
• bfs를 돌릴 때 시작지점과 도착지점이 모두 다르므로 인자로 넘겨서 큐에 넣고 탐색
• 이후 한 개라도 도달 할 수 없는 경우가 있다면 -1, 목적지까지 도달 할 수 있다면 시간 반환

코드

from collections import deque

# 상하좌우
dy = [-1,1,0,0]
dx = [0,0,-1,1]

def solution(maps):
    
    # start 부터 end까지의 거리 측정
    def bfs(start, end):
        start_flag = False
        n = len(maps)
        m = len(maps[0])
        visited = [[0] * m for _ in range (n)]
        queue = deque()
        
        # 시작 지점 찾기
        for i in range(n):
            for j in range(m):
                # 시작지점 찾은 후 종료
                if maps[i][j] == start:
                    start_flag = True
                    queue.append((i,j, 0))
                    visited[i][j] = 1
                    break
            # 시작지점 찾은 후 바깥 루프도 종료
            if start_flag:
                break
    
        
        # 도착지점 까지의 거리 체크
        while queue:
            y, x, cost = queue.popleft()
            if maps[y][x] == end:
                return cost
            for i in range(4):
                ny = y + dy[i]
                nx = x + dx[i]
                # 범위 내에 있는지 체크
                if 0 <= ny < n and 0 <= nx < m and not visited[ny][nx] and maps[ny][nx] != 'X':
                    visited[ny][nx] = 1
                    queue.append((ny, nx, cost + 1))
                    
        return False
    
    lever = bfs('S','L')
    arrive = bfs('L','E')
    
    if lever and arrive:
        answer = lever + arrive
    else:
        answer = -1
        
    return answer