[알고리즘] 프로그래머스 Lv2 미로 탈출

문제

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

풀이과정

문제를 이해하는데 시간이 걸렸다.
처음에 "이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다."를 보고 출구타일을 지나가기만 하면 탈출이 가능하다고 생각했는데, 다시 보니 문은 레버에서 열 수 있는 것이었다.
한번 지나간 칸을 또 갈 수 있다는 점 또한 알고리즘을 작성할 때 중요한 포인트였다.
최단시간이므로 다익스트라 알고리즘처럼 visited +1 보다 다음 타일에 있는 수가 크면 이동하도록 작성했다(아래의 코드 참고)

코드는 시작, 레버, 도착 지점의 좌표를 구한 후, 시작->레버 최단시간 + 레버->출구 최단시간을 구하는 방식으로 작성했다.

이렇게 풀이하니 시간초과가 2개의 테스트 케이스에서 떴다.
BFS에서 시간초과 뜨면 뭐다? => deque로 바꿔본다. 통과!
파이썬은 알고리즘을 풀기 정말 편한 언어인 것 같다...ㅎ

코드

from collections import deque

def solution(maps):
    def BFS(point):
        dx = [0, 1, 0, -1]
        dy = [1, 0, -1, 0]
        R, C = len(maps), len(maps[0])
        visited = [[False] * C for _ in range(R)]
        queue = deque([point])
        visited[point[0]][point[1]] = True

        while queue:
            x, y = queue.popleft()
            for k in range(4):
                nx, ny = x + dx[k], y + dy[k]
                if (0 <= nx < R) and (0 <= ny < C) and maps[nx][ny] != 'X':
                    if not visited[nx][ny] or visited[nx][ny] > visited[x][y] + 1:
                        queue.append([nx, ny])
                        visited[nx][ny] = visited[x][y] + 1

        return visited

    for i in range(len(maps)):
        if 'S' in maps[i]:
            start = [i, maps[i].find('S')]
        if 'E' in maps[i]:
            end = [i, maps[i].find('E')]
        if 'L' in maps[i]:
            lever = [i, maps[i].find('L')]

    start_lever = BFS(start)
    if start_lever[lever[0]][lever[1]] == False:
        return -1
    else:
        lever_end = BFS(lever)
        if lever_end[end[0]][end[1]] == False:
            return -1
        else:
            return start_lever[lever[0]][lever[1]] -1 + lever_end[end[0]][end[1]] - 1


maps = ["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]
maps = ["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"]
maps = ["SOOOOL","XXXOXO","OOOOOO","OXXOXX","OOOOEO"]
print(solution(maps))

다른 사람의 풀이

특별히 다른 코드를 찾지 못해서 PASS~