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

from collections import deque

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def solution(maps):
    q = deque()
    temp = [[False] * len(maps[0]) for _ in range(len(maps))]
    graph = [[False] * len(maps[0]) for _ in range(len(maps))]

    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j] == 'S':
                q.append((i, j))
                temp[i][j] = 0
            if maps[i][j] == 'L':
                lever = (i, j)
            if maps[i][j] == 'E':
                end_x, end_y = (i, j)

    # lever
    while q:
        x, y = q.popleft()
        if (x, y) == lever:
            q.clear()
            q.append((x, y))
            graph[x][y] = temp[x][y]
            break

        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < len(maps) and 0 <= ny < len(maps[0]):
                if maps[nx][ny] != 'X' and not temp[nx][ny]:
                    temp[nx][ny] = temp[x][y] + 1
                    q.append((nx, ny))

    # exit
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < len(maps) and 0 <= ny < len(maps[0]):
                if maps[nx][ny] != 'X' and not graph[nx][ny]:
                    graph[nx][ny] = graph[x][y] + 1
                    q.append((nx, ny))

    if not graph[end_x][end_y]:
        return -1
    return graph[end_x][end_y]

2. 후기

시간복잡도가 충분히 여유있기 때문에 출발지점과 레버 두 지점에서 BFS를 각각 사용하여 안전하게 풀었다.