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

문제)

 

 

알고리즘)

- BFS(너비우선탐색)

- 두번의 BFS를 활용해서 문제를 해결함

- 첫번째 BFS는 "S"부터 출발해서 "L"를 목적지로 수행

- 두번째 BFS는 "L"부터 출발해서 "E"를 목적지로 수행 

-이를 수행하는동안 이동한 횟수 출력

 

코드)

from collections import deque
def solution(maps):
    a = bfs("S", "L", maps)
    b = bfs("L", "E", maps)
    if a == -1 or b == -1:
        return -1
    else:
        return a+b
        
def bfs(start, end, maps):
    n, m = len(maps), len(maps[0])
    m_y = [1, 0, -1, 0]
    m_x = [0, 1, 0, -1]
    n, m = len(maps), len(maps[0])
    q = deque()
    for i in range(n):
        for j in range(m):
            if maps[i][j] == start:
                q.append([i, j])
                break
    visited = [[0]*m for _ in range(n)]
    while q:
        y, x = q.popleft()
        for i in range(4):
            n_y, n_x = y+m_y[i], x+m_x[i]

            if not((0 <= n_y < n) and (0 <= n_x < m)):
                continue

            if maps[n_y][n_x] == "X" or visited[n_y][n_x] != 0:
                continue
            
            q.append([n_y, n_x])
            visited[n_y][n_x] = visited[y][x] + 1

            if maps[n_y][n_x] == end:
                return visited[n_y][n_x]
    return -1