99클럽 코테 스터디 5일차 TIL + bfs (너비우선탐색)

https://www.acmicpc.net/problem/24444

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

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

for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)


def bfs(r):
    global seq
    visited[r] = seq
    seq += 1
    que = [r]
    while que:
        q = que.pop(0)
        graph[q].sort()
        for i in graph[q]:
            if visited[i] == 0:
                visited[i] = seq
                seq += 1
                que.append(i)


bfs(r)
for i in range(1, n+1):
    print(visited[i])

• BFS

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
3. 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다.