[알고리즘]프로그래머스, 미로 탈출(BFS)

프로그래머스에서 bfs문제를 더 풀어보고 싶어서 '미로탈출'이라는 제목만 보고 골랐는데 진짜 bfs문제다

아이디어

최종 탈출시간을 구하는 전형적인 bfs 구현 문제이며 리코쳇 문제와 같은 문제나 다름없다..start 지점에서 레버 지점까지 가서 exit의 문을 열고, 레버 지점에서 exit로 나가면 된다.

시간 복잡도

세로N,가로M인 2차원 맵에서 상하좌우 4방향으로 움직이므로 방문체크없이 bfs를 사용하면 시간복잡도는 O(4NM)이다.하지만 방문체크를 한다면 모든 정점을 방문하는 시간 + 모든 간선을 확인하는 시간만큼 걸리므로 O(2NM)이다. 결국 상수배를 무시할 수 있으므로 O(NM)만큼 걸린다.

코드

from collections import deque

def bfs(start, end, maps):
    #상하좌우
    direction = [(0,-1),(0,1),(-1,0),(1,0)]
    n,m = len(maps),len(maps[0])
    visited = [[False]*m for _ in range(n)]
    que = deque()
    flag = False
    
    #출발지점을 스택에 넣고 시작
    for i in range(n):
        for j in range(m):
            if maps[i][j] == start:
                que.append((i,j,0))
                visited[i][j] = True
                flag = True;
                break
        if flag:
            break
    
    #bfs알고리즘
    while que:
        y, x, cost = que.popleft()
        
        if maps[y][x] == end:
            return cost
        
        for ay,ax in direction:
            ny, nx = y+ay, x+ax
            
            if (ny>=0 and ny<n and nx>=0 and nx<m and maps[ny][nx] != "X"):
                if (not visited[ny][nx]):
                    que.append((ny,nx,cost+1))
                    visited[ny][nx] = True
    return -1

def solution(maps):
    path1 = bfs('S','L',maps) 
    path2 = bfs('L','E',maps) 
    
    if path1 != -1 and path2 != -1:
        return path1+path2
    
    return -1

참고자료

https://www.acmicpc.net/board/view/47137
https://school.programmers.co.kr/learn/courses/30/lessons/159993/solution_groups?language=python3