Programmers / 2단계 / 미로 탈출 / python

 

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

 

 

코드

from collections import deque

def bfs(start, end, maps):
    dy = [0, 1, -1, 0]
    dx = [1, 0, 0, -1]
     
    n = len(maps)      
    m = len(maps[0])    
    visited = [[False] * m for _ in range(n)]
    q = deque()
    
    for i in range(n):
        for j in range(m):
            if maps[i][j] == start:      
                q.append((i, j, 0))    
                visited[i][j] = True
                
    while q:
        y, x, cost = q.popleft()
        
        if maps[y][x] == end:
            return cost
        
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            
            if 0<= ny <n and 0<= nx <m and maps[ny][nx] !='X':
                if not visited[ny][nx]:	
                    q.append((ny, nx, cost+1))
                    visited[ny][nx] = True
                    
    return -1	
        
            
def solution(maps):
    lever = bfs('S', 'L', maps)	
    exit = bfs('L', 'E', maps) 
   
    if lever != -1 and exit != -1:
        return lever + exit
        
    return -1

 

 최소 시간 = 최소 거리를 구하는 문제이기 때문에 BFS를 사용하여 접근하였다.