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

문제

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

접근 방법

• 최단 거리 구하기, 경로 비용 모두 1 -> BFS 사용
• 경유 노드(레버)가 있기 때문에 bfs 두번 쓴다.
  • bfs(시작노드, 레버) + bfs(레버, 문)

정답 코드

from collections import deque


def bfs(start, end, maps):
    queue = deque()
    queue.append((start[0], start[1], 0))
    
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    visited = [[0] * len(maps[0]) for i in range(len(maps))]
    visited[start[0]][start[1]] = 1
    
    
    while queue:
        x, y, cnt = queue.popleft()
        if end == [x,y]:
            return cnt
        
        for i in range(4):
            ax, ay = x+dx[i], y+dy[i]
            if 0 <= ax < len(maps) and 0<= ay < len(maps[0]) and maps[ax][ay] != 'X':
                if visited[ax][ay] == 0:
                    visited[ax][ay] = 1
                    queue.append([ax, ay, cnt+1])
    return 0
    

def solution(maps):
    answer = 0
    global s, l, e
    s = []
    l = []
    e = []

    
    for i in range(len(maps)):
        for j in range(len(maps[0])):
            if maps[i][j] == 'S':
                s = [i,j]
            elif maps[i][j] == 'L':
                l = [i,j]
            elif maps[i][j] == 'E':
                e = [i,j]
                
    st = bfs(s,l, maps)
    le = bfs(l,e, maps)
    
    if st != 0 and le != 0:
        answer = st + le
    else:
        answer = -1
        
    return answer

참고

DFS/BFS