프로그래머스 미로탈출

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

프로그래머스

 

문제 설명

---

1. " 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다." 

 

출구는 "미로를 빠져나가는 문" 이다.

---

2. " 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다"

 

이 말은 레버가 당겨지지 않았더라면 출구가 있는 칸을 지나 갈 수 있을 뿐 미로를 빠져나갈 수 없다는 것이다.

---

3. 구하고자 하는 것: "최대한 빠르게 미로를 빠져나가는데 걸리는 시간"

 

"최대한 빠르게 출구까지 가는데 걸리는 시간" 이 아니라 "최대한 빠르게 미로를 빠져나가는데 걸리는 시간" 이다.

따라서 "출발지점에서 레버까지 거리 + 레버에서 출구까지의 거리" 를 구해야한다.

 

 

from collections import deque

board = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
sx, sy, ex, ey, lx, ly = 0, 0, 0, 0, 0, 0


def bfs(x, y, n, m, target):
    q = deque()
    visited = [[-1 for _ in range(m)] for _ in range(n)]
    visited[x][y] = 0
    q.append((x, y))
    while q:
        x, y = q.popleft()
        if board[x][y] == target:
            break
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if (
                0 <= nx < n
                and 0 <= ny < m
                and board[nx][ny] != "X"
                and visited[nx][ny] == -1
            ):
                visited[nx][ny] = visited[x][y] + 1
                q.append((nx, ny))
    if target == "L":
        return visited[lx][ly]
    return visited[ex][ey]


def solution(maps):
    global sx, sy, ex, ey, lx, ly
    n = len(maps)
    m = len(maps[0])
    for i in range(n):
        board.append(list(maps[i]))
    for i in range(n):
        for j in range(m):
            if board[i][j] == "S":
                sx, sy = i, j
            if board[i][j] == "E":
                ex, ey = i, j
            if board[i][j] == "L":
                lx, ly = i, j
    toLever = bfs(sx, sy, n, m, "L")
    leverToExit = bfs(lx, ly,n, m, "E")
    if toLever == -1 or leverToExit == -1 :
        return -1
    else:
        return toLever+leverToExit