BFS

큐를 사용하는 것보다 deque 를 이용해 큐처럼 사용하는게 편하다.
방법
왼쪽에서 입/출력: appendleft(val), popleft()
오른쪽에서 입/출력: appeend(val), pop()
(오른쪽에서의 입/출력이 기본이고 왼쪽인 경우 'left' 가 붙는다.)

주의 사항
큐에 삽입 => 실제 방문으로 생각하고 방문처리 해야 한다.
즉, 첫 노드 삽입 때(while 문 이전) 방문 처리를 해줘야 하고, 이후 while 문을 돌면서 인근 노드들을 큐에 삽입할 때 함께 방문 처리를 해줘야 한다.

큐에 삽입 시 실제 방문을 할 수 있는 이유
방문가능지역 검사에서 만난 순서와 실제 탐색 지역의 순서가 일치하기 때문

# BFS
from collections import deque
def bfs(graph, r, visited):
    # 큐 사용
    queue = deque()
    # 큐에 시작 노드 삽입 & 방문 처리
    queue.append(r)
    visited[r] = True
    print(r)
    # 큐가 빌때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력
        v = queue.popleft()
        # 해당 원소와 연결된, 아직 방문하지 않은 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]: # 인접한 노드중 방문하지 않은 노드를 "모두" 큐에 넣음
                queue.append(i) # 삽입
                visited[i] = True # 방문 처리
                print(i)

*매개변수에 graph, visited 안넣어줘도 인식함

2025.07.24 후기

헷갈리지 말자.
24445 알고리즘 수업 - 너비 우선 탐색 2

import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

n, m ,r = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [0 for _ in range(n+1)]

for _ in range(m):
    f, s = map(int, input().split())
    graph[f].append(s)
    graph[s].append(f)
for arr in graph:
    arr.sort(reverse=True)
print(graph)

def bfs(graph, visited, cur_node):
    cnt = 1
    queue = deque()
    queue.append(cur_node)
    visited[cur_node] = cnt
    cnt += 1 

    while(queue):
        v = queue.popleft()

        for nv in graph[v]:
            if visited[nv] == 0:
                queue.append(nv)
                visited[nv] = cnt
                cnt+=1

bfs(graph, visited, r)
for val in visited[1:n+1]: print(val)