[프로그래머스] 미로 탈출

문제

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

풀이

bfs를 두 번 사용하여 푼 풀이

출발점부터 레버까지 가는 최소 경로를 bfs로 구하고
레버부터 탈출구까지 가는 최소 경로를 bfs로 구한 뒤

두 최소 경로를 합하여 값을 출력한다

만약 갈 수 없는 경우 -1 를 반환하고
즉시 -1를 결과값으로 반환한다.

from collections import deque


def bfs(maps, start_y, start_x, target):
    queue = deque([[start_y, start_x, 0]])
    visited = [[False] * len(maps[0]) for _ in range(len(maps))]
    visited[start_y][start_x] = True

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

    while queue:
        cur_y, cur_x, count = queue.popleft()

        for i in range(4):
            next_y = cur_y + dy[i]
            next_x = cur_x + dx[i]

            if 0 <= next_y < len(maps) and 0 <= next_x < len(maps[0]) and not visited[next_y][next_x]:
                if maps[next_y][next_x] == "X":
                    continue
                queue.append([next_y, next_x, count + 1])
                visited[next_y][next_x] = True
             if maps[next_y][next_x] == target:
                    return next_y, next_x, count + 1

    return cur_y, cur_x, -1


def solution(maps):
    answer = 0
    max_row, max_col = (len(maps), len(maps[0]))

    cur_y, cur_x = 0, 0

    for r in range(max_row):
        for c in range(max_col):
            if maps[r][c] == "S":
                cur_y, cur_x = r, c

    cur_y, cur_x, L_count = bfs(maps, cur_y, cur_x, "L")
    if L_count == -1:
        return -1

    cur_y, cur_x, E_count = bfs(maps, cur_y, cur_x, "E")
    if E_count == -1:
        return -1
  
    return L_count + E_count