문제출처 : https://www.acmicpc.net/problem/24444
난이도 : 실버 2

---

문제 파악

알고리즘 수업 - 깊이 우선 탐색 1 문제에 이어서 너비 우선 탐색 문제이다.

정점의 수 N, 간선의 수 M, 시작 정점 R과
간선 정보 u,v(u->v) 를 입력받아서 방문 순서를 차례로 출력하면 된다.

인접 정점은 오름차순으로 방문한다고 주어졌다.

---

DFS랑 입력 구조는 거의 똑같고, “다음 정점을 고르는 방식”만 다르다.
DFS는 한 갈래로 끝까지 파고들고,
BFS는 가까운 정점부터 차례대로 퍼져나간다(큐/Queue).

이번 문제는 “너비 우선 탐색”이라서 큐(deque) 를 쓰는 게 핵심이다.

---

1. 입력 그래프 구성 + 오름차순 정렬

입력은 무방향 그래프라서 DFS 때처럼
graph[u].append(v)
graph[v].append(u)
양쪽에 다 넣어준다.

그리고 문제 조건이 “인접 정점은 오름차순 방문”이니까
각 정점의 인접 리스트를 sort()로 정렬해준다.

---

2. 방문 체크 배열 + 방문 순서 저장 배열 준비

DFS에서는 visited에 방문 순서를 바로 저장했는데,
이번에는 BFS라서 방문 여부와 방문 순서 기록을 분리해도 깔끔하다.

visited: 이미 큐에 넣었는지(방문 처리됐는지) 확인용
order: 각 정점이 몇 번째로 방문됐는지 저장용

방문하지 않은 정점은 order가 0인 채로 남는다.

---

3. BFS

• 시작 정점을 큐에 넣고 방문 처리
• 큐에서 하나 꺼낸 뒤
• 그 정점의 인접 정점 중 “아직 방문 안 한 애들”을 큐에 넣는다
• 큐가 빌 때까지 반복한다.

이 방식 때문에 “가까운 정점 → 그 다음 거리 정점” 순서로 방문이 보장된다.
그리고 방문 순서는 변수 cnt를 하나 만들어 처리한다.

시작 정점: 1
새로 방문할 때마다 cnt += 1

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

N, M, R = map(int, input().split())

graph = [[] for _ in range(N + 1)]

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

for i in range(1, N + 1):
    graph[i].sort()

visited = [False] * (N + 1)
order = [0] * (N + 1)
cnt = 1

def bfs(start):
    global cnt
    queue = deque([start])
    visited[start] = True
    order[start] = cnt

    while queue:
        node = queue.popleft()

        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                cnt += 1
                order[neighbor] = cnt
                queue.append(neighbor)

bfs(R)

for i in range(1, N + 1):
    print(order[i])