10. 그래프 - 너비 우선 탐색(BFS, Breadth First Search)

타겟 넘버 - https://school.programmers.co.kr/tryouts/85939/challenges

그냥 리스트 사용하면 시간 초과 → deque 사용

리스트: pop(0) = O(N) → 제거하고 모든 원소 왼쪽으로 옮김

dqeue: popleft = O(1) → 이중 연결 리스트로 구현되어 있어 양 끝 삭제 효율적

from collections import deque
def solution(numbers, target):
    queue = deque([(sum(numbers), 0)])  
    cnt = 0
    numbers.sort(reverse=True)
    while queue: 
        cur_sum, i = queue.popleft()
        
        if i == len(numbers):
            if cur_sum == target:
                cnt += 1
        elif cur_sum >= target:
            num = numbers[i]
            queue.append([cur_sum, i+1])
            queue.append([cur_sum - num * 2, i+1])
        
    return cnt

 

---

게임 맵 최단거리 - https://school.programmers.co.kr/tryouts/85940/challenges

from collections import deque
def solution(maps):
    dx = [1, -1, 0, 0] # 아래 위 오 왼
    dy = [0, 0, 1, -1] # 아래 위 오 왼
    n, m = len(maps), len(maps[0])
    table = [[-1 for _ in range(m)] for _ in range(n)]
    table[0][0] = 1
    queue = deque([[0, 0]])
    while queue:
        x, y = queue.popleft()
        cur_cost = table[x][y]
        for i in range(4):
            xx = x + dx[i]
            yy = y + dy[i]
            if 0<=xx<n and 0<=yy<m and maps[xx][yy] == 1:
                if cur_cost + 1 < table[xx][yy] or table[xx][yy] == -1:  
                    table[xx][yy] = cur_cost + 1
                    queue.append([xx, yy])
    return table[n-1][m-1]