6119 : BFS 레이어별 처리
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
정점 N개와 간선 M개인 무방향 그래프가 주어집니다. 시작 노드 S에서 시작하여 너비 우선 탐색(BFS)을 수행할 때, 각 레벨(시작 노드와의 최단 거리)별로 속해 있는 노드의 개수를 거리순으로 구하는 프로그램을 작성하십시오.
거리 0(시작 노드)부터 시작하여 순서대로 출력합니다.
거리 0(시작 노드)부터 시작하여 순서대로 출력합니다.
입력 설명
첫째 줄에 정점 수 N (1 ≤ N ≤ 1,000)과 간선 수 M (1 ≤ M ≤ 5,000)이 주어집니다.
둘째 줄부터 M개의 줄에 무방향 간선 u v가 주어집니다.
마지막 줄에는 시작 노드 S가 주어집니다.
둘째 줄부터 M개의 줄에 무방향 간선 u v가 주어집니다.
마지막 줄에는 시작 노드 S가 주어집니다.
출력 설명
레벨 0부터 도달 가능한 최대 레벨까지 각 레벨에 도달하는 노드의 총 개수를 공백으로 구분하여 한 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 3
1 2
2 3
3 4
1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1 1 1 1도움
BFS 탐색 시 큐에 있는 원소의 개수를 측정한 뒤, 그 크기만큼 큐에서 꺼내어 인접 노드를 삽입하는 루프를 감싸서 수행하면 레벨(계층) 단위로 쉽게 동기화하여 데이터를 수집할 수 있습니다.