프로그래머스 - 미로 탈출

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

프로그래머스

 

델타 탐색 문제

 

4방향으로 움직이며 갈 수 있는가와 레버를 찍고 도착 지점에 도착하는 문제

시간 단위로 움직이니까 DFS던 BFS던 visited 배열을 만들고 지나간 곳은 몇 초만에 왔는지를 생각하면 된다.

하지만 함정이 있는데 레버를 당겨야지 도착할 수 있고 지나갔던 길도 다시 지나갈 수 있다.

 

때문에 visited 배열을 넘기며 어차피 갔던 길을 3번 이상 지나가는 일은 절대 없을 것이기 때문에 이에 대한 조건을 걸고 재귀함수로 구현했는데 시간초과가 났다.

어떻게 해결해야할까를 생각해봤는데 2차원 배열을 계속 넘기는 재귀를 굳이할 필요가 없다.

 

visited를 해당 칸으로 이동할 수 있는 최단 시간으로 update하며

레버에 도착하는 최선의 경로에 대한 탐색을 먼저 하고

출구에 대한 최선의 경로를 탐색하면 중복 처리에 대한 코드가 필요가 없어진다.

 

0. 먼저 maps의 테두리에 "X"로 감싸준다. -> 0번인 이유는 매 요청마다 유효 범위인지 if문으로 검사해도 되기 때문

1. maps와 같은 크기의 visited를 만든다. 유효한 시간의 최대크기는  100*100라고 생각해서 10000으로 지정

2. S의 위치를 찾고 L에 대한 BFS 시작

3. L을 찾아가면서 visited의 요소를 가장 짧은 소요 시간으로 update해주고

4. L을 찾았다면 lever_position을 해당 좌표로 업데이트 해주고

4-1 못찾으면 -1을 return

5. visited를 초기화해주고 lever_position에 해당하는 좌표만 레버까지의 최적 경로 시간으로 update

6. 똑같이 E에 대한 BFS를 시작

7. visited를 update 해가며 E를 찾고

8. E를 찾았다면 end_point를 업데이트하고

8-1. 못찾았다면 -1을 return

9. answer update

 

from collections import deque

def solution(maps):
    answer = 0
    start = 0
    visited = [[10000 for _ in range(len(maps[0]) + 2)] for _ in range(len(maps) + 2)]
    
    for y in range(len(maps)):
        maps[y] = ["X"] + list(maps[y]) + ["X"]
        for x in range(len(maps[0])):
            if not start and maps[y][x] == "S":
                start = (y+1,x,0)
    
    maps = [["X" for _ in range(len(maps[0]))]] + maps + [["X" for _ in range(len(maps[0]))]]
    
    d = [(0,1),(0,-1),(-1,0),(1,0)]
    
    q = deque([start])
    lever_position = 0
    
    while q:
        y,x,time = q.popleft()
        for dy, dx in d:
            ny = y + dy
            nx = x + dx
            if maps[ny][nx] == "X":
                pass
            elif visited[ny][nx] > time + 1:                
                visited[ny][nx] = time + 1
                if maps[ny][nx] == "L":
                    lever_position = (ny,nx,visited[ny][nx])
                    pass
                else:
                    q.append((ny,nx,time+1))
                    
    if not lever_position:
        return -1
    
    visited = [[10000 for _ in range(len(maps[0]))] for _ in range(len(maps))]
    visited[lever_position[0]][lever_position[1]] = lever_position[2]
    
    q = deque([lever_position])
    end_point = 0
    
    while q:
        y,x,time = q.popleft()
        for dy, dx in d:
            ny = y + dy
            nx = x + dx
            if maps[ny][nx] == "X":
                pass
            elif visited[ny][nx] > time + 1:                
                visited[ny][nx] = time + 1
                if maps[ny][nx] == "E":
                    end_point = (ny, nx)
                else:
                    q.append((ny,nx,time+1))
    
    if not end_point:
        return -1
    else:
        answer = visited[end_point[0]][end_point[1]]
        
    return answer