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

1. 문제 

https://school.programmers.co.kr/learn/courses/30/lessons/159993#

프로그래머스

 

2. 알고리즘

1. 해당 글은 최단 거리를 찾아야 하므로 bfs가 적합

2. 지도의 조건이 중요한데, X를 제외한 모든 칸은 다 여러번 지나다닐 수 있다

3. 먼저 시작지점, 출구, 레버의 위치를 저장한다

4. 시작 - 레버위치의 최단거리를 구한다 

5. 모든 통로는 X를 제외하고 지나 다닐 수 있으므로, 레버까지의 최소이동 거리를 제외하고 지나온 경로를 초기화 시킨다 

6. 레버의 위치 - 출구까지의 최단거리를 구한다

7. 출구의 위치에 저장된 최단거리 -1 반환

3. 코드

from collections import deque

def solution(maps):    
    n, m = len(maps[0]), len(maps)
    visited = [[0] * n for _ in range(m)]
   
    def bfs(move, x,y, dest_x, dest_y):
        q = deque()
        q.append((x,y))
        visited[x][y] = move
        
        while q:
            cur_x, cur_y = q.popleft()
            if cur_x == dest_x and cur_y == dest_y:  
                return 0
            for dx, dy in [(1,0), (-1,0), (0,-1), (0,1)]:
                nx, ny = cur_x + dx, cur_y + dy
                
                if not (0 <= nx < m and 0 <= ny < n): continue

                if maps[nx][ny] != 'X' and visited[nx][ny] == 0:
                    q.append((nx, ny))
                    visited[nx][ny] = visited[cur_x][cur_y] + 1
        return -1                
    
    # 필요한 지점 위치 찾기 
    switch_x, switch_y = 0, 0
    start_x, start_y = 0, 0
    end_x, end_y = 0, 0
    for i in range(len(maps)):
        for j in range(len(maps[i])):
            if maps[i][j] == 'L': #레버의 위치
                switch_x, switch_y = i, j
            if maps[i][j] == 'S': #시작지점의 위치
                start_x, start_y = i, j
            if maps[i][j] == 'E': #종료지점의 위치 
                end_x, end_y = i,j 
                
    #출발 - 레버 도달 
    if bfs(1, start_x, start_y, switch_x, switch_y) == -1: 
        return -1 #레버 도달이 불가능한 경우 
    
    cur = visited[switch_x][switch_y]
    visited = [[0] * n for _ in range(m)]
    #레버로 - 도착지점 도달 
    if bfs(cur, switch_x, switch_y, end_x, end_y) == -1:
        return -1 # 목적지 도달이 불가능 한 경우 
    
    return visited[end_x][end_y]-1