[프로그래머스] 미로탈출 파이썬

문제 설명

1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

---

제한사항

• 5 ≤

  maps

의 길이 ≤ 100

• 5 ≤ maps[i]의 길이 ≤ 100

• maps[i]

  는 다음 5개의 문자들로만 이루어져 있습니다.

  • S : 시작 지점
  • E : 출구
  • L : 레버
  • O : 통로
  • X : 벽

• 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.

• 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

---

입출력 예

maps	result
["SOOOL","XXXXO","OOOOO","OXXXX","OOOOE"]	16
["LOOXS","OOOOX","OOOOO","OOOOO","EOOOO"]	-1

제출 답안

• start에서 lever까지 거리와 lever에서 end까지 거리를 구해서 더하면 된다.
• 그러긴 위해서 start와 lever의 좌표가 필요하다.
  • 이 함수가 get_point다.
• 그 다음에는 bfs를 사용해서 거리를 찾아가면 된다.
  • 이 때 거리는 계속해서 같이 저장해준다.
  • 열 다음에 행으로 접근하기 때문에 bfs나 dfs를 사용할 때 y, x순으로 적는 편이다.
• lever까지 거리와 end까지 거리 모두 -1보다 크면 값을 더해서 반환한다.
  • 그렇지 않으면 -1을 반환한다.

from collections import deque

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

def get_point(maps:list)->tuple:
    start, lever = 0, 0
    for i, val in enumerate(maps):
        if "S" in val:
            start = (i, val.index("S"))
        if "L" in val:
            lever = (i, val.index("L"))
    return start, lever

def bfs(start:tuple, maps:list, target:str) -> int:
    col, row = len(maps), len(maps[0])
    y, x = start
    visited = [[False] * row for _ in range(col)]
    visited[y][x] = True
    q = deque([(y, x, 0)])
    while q:
        y, x, dist = q.popleft()
        if maps[y][x] == target:
            return dist
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0<=ny<col and 0<= nx <row:
                if maps[ny][nx] != 'X' and not visited[ny][nx]:
                    visited[ny][nx] = True
                    q.append((ny, nx, dist+1))
    return -1


def solution(maps:list) -> int:
    start, lever = get_point(maps)
    l_dist = dfs(start, maps, 'L')
    e_dist = dfs(lever, maps, "E")
    if l_dist > -1 and e_dist > -1:
        answer = l_dist + e_dist
    else:
        answer = -1
    return answer