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

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

n, m, r = map(int, input().split()) # 정점의 수, 간선의 수, 시작 노드 번호
visited = [0] * (n+1) # 방문 체크 여부 배열
graph = [ [] for _ in range(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 list in graph:
    list.sort()
# bfs 탐색
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 # v번 노드 출력 순서 기록
        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(str(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(n+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 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)