[백준] 24445 알고리즘 수업 - 너비 우선 탐색 2

import sys
input = sys.stdin.readline
from collections import deque

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

ans = [0] * (n+1)
ans_idx = 1

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
for lst in graph:
    lst.sort(reverse=True)
    
def bfs(graph, r, visited):
    queue = deque()
    # 첫번째 노드 삽입 & 방문 처리
    queue.append(r)
    visited[r] = True
    while queue:
        # 출력
        global ans_idx
        v = queue.popleft()
        ans[v] = ans_idx # 출력 노드 순서 저장
        ans_idx += 1
        for i in graph[v]: # 방문 안한 인접한 노드들 모두 삽입 & 방문 처리
            if visited[i] == 0: 
                queue.append(i)
                visited[i] = True

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

다시 풀기

1
방문 여부에 방문 순서를 포함시킬 수 있다는 것을 알게 되었다.

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

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

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

for arr in graph:
    arr.sort()

from collections import deque

cnt = 1
def bfs_que(graph, visited, r):
    queue = deque([])
    queue.append(r) # 넣고
    global cnt
    visited[r] = cnt # 방문 처리
    cnt+=1

    while queue:
        v = queue.popleft()
        for nv in reversed(graph[v]):
            if visited[nv] == 0:
                queue.append(nv) # 넣고
                visited[nv] = cnt # 방문 처리
                cnt+=1

bfs_que(graph, visited, r)
for v in visited[1:]:
    print(v)