프로그래머스 Lv2 | dfs/bfs | 게임 맵 최단거리

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

프로그래머스

 

 

queue visited 처리하는걸

넣자마자 하지 않고 빼낼 때 하면 시간 초과가 뜬다 처음 알았음 ㅇㅁㅇ

 

<예시>

1 1
1 1

위와 같은 예시일 때

1. pop이후에 visited 처리하면

queue = [(0,0)]

queue = [(0,1), (1,0)]

queue = [(1,0), (1,1)]

queue = [(1,1), (1,1)] <<< 두번 들어감

2. queue 넣자마자 visited 처리하면

queue = [(0,0)]

queue = [(0,1), (1,0)]

queue = [(1,0), (1,1)]

queue = [(1,1)]

 

from collections import deque
def bfs(x, y, maps, n, m, cnt):
    queue = deque([(x,y,cnt)]) # 처음 시작 (0,0,1)
    maps[x][y] = 2 # 방문 처리
    # 상/하/좌/우
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    
    while queue:
        x, y, cnt = queue.popleft()
        if x == n-1 and y == m-1: # 종료 조건
                return cnt
        
        for i in range(4): # 다음 위치에 갈 수 있는 후보들
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < m: # 위치가 범위 안에 있어야 함
                if maps[nx][ny] == 1: # 방문한 적이 없고(2) 벽이 아니어야 함(0)
                    queue.append((nx, ny, cnt+1))
                    maps[nx][ny] = 2 # 방문 처리
    # 갈 수 없는 경로일 때 (queue를 다 비웠는데도 종료 조건 성립을 안 함)
    return -1
    
def solution(maps):
    # 최단거리 문제 -> bfs 접근
    # 도착할 수 없을 때는 -1 반환
    # 출발 (0,0) -> 도착 (n-1, n-1)
    n, m = len(maps), len(maps[0])
    answer = bfs(0, 0, maps, n, m, 1)
    return answer