BFS
Coddy의 그래프 - 자료구조 시리즈 #9 코스 레슨 — 14개 중 10번째.
다음 챌린지들은 여러분이 방금 구축한 Graph 클래스를 사용하도록 설계되었습니다.
각 챌린지는 잠겨 있는 graph 파일(이전 챕터의 최종 Graph)과 Graph를 사용하는 함수를 작성할 새로운 solution 파일을 제공합니다.
우리의 첫 번째 알고리즘은 너비 우선 탐색(Breadth-First Search)입니다. 정점(vertex)에서 시작하여, BFS는 도달 가능한 모든 정점을 파동 형태로 방문합니다. 먼저 시작점, 그다음은 한 간선(edge) 거리의 모든 것, 그다음은 두 간선 거리의 모든 것 순으로 진행됩니다. 전형적인 구현 방식은 큐(queue)를 사용합니다. 시작점을 인큐(enqueue)하고, 반복적으로 디큐(dequeue)하며, 해당 정점을 방문한 것으로 기록하고, 방문하지 않은 이웃들을 인큐합니다.
이웃 목록은 고정된 순서가 없기 때문에, 두 개의 올바른 BFS 실행 결과가 서로 다른 탐색 순서를 생성할 수 있습니다. 이 챌린지에서 정답을 결정론적으로 만들기 위해, 각 정점의 이웃들을 인큐하기 전에 오름차순으로 정렬하세요.
챌린지
쉬움2D 정수 배열 adjacency(각 행은 [u, v] 간선임)와 정수 start를 입력받아, start로부터의 BFS 방문 순서를 정수 리스트로 반환하는 함수 bfs를 작성하세요.
그래프 구축: adjacency의 각 [u, v]에 대해 g.addEdge(u, v)를 호출하세요. 그런 다음 큐를 사용하여 start로부터 BFS를 수행합니다. 정점의 이웃을 처리할 때, 출력이 결정론적이 되도록 오름차순으로 정렬하세요.
반드시 Graph 클래스(graph에 제공됨)를 사용해야 합니다. 인접 리스트를 모델링하기 위해 언어 내장 기능(맵, 셋)을 사용하지 마세요. 알고리즘을 위한 보조 데이터(방문 확인용 셋, 큐)는 표준 라이브러리 타입을 사용할 수 있습니다.
직접 해보기
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start;
if (scanf("%d %d %d", &n, &m, &start) != 3) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
int out[MAX_VERTICES];
int outn = bfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}