DFS
Coddy의 그래프 - 자료구조 시리즈 #9 코스 레슨 — 14개 중 11번째.
깊이 우선 탐색(Depth-First Search)은 옆으로 넓게 가기 전에 깊게 들어갑니다. 정점에서 시작하여 가능한 한 멀리 하나의 간선을 따라간 다음, 되돌아와서(backtrack) 다음 간선을 시도합니다. 반복문 버전은 스택(stack)을 사용합니다. 정점을 꺼내고(pop), 기록한 다음, 방문하지 않은 이웃 정점들을 다시 넣습니다(push).
이 챌린지에서 DFS가 결정론적인 순회 순서를 생성하도록 하려면, 이웃 정점들을 역순으로 정렬하여(reverse-sorted) 넣으세요. 그렇게 하면 가장 작은 이웃 정점이 스택의 맨 위에 놓여 가장 먼저 처리되며, 이는 오름차순 이웃에 대한 재귀적 DFS가 생성하는 순서와 일치하게 됩니다.
정점이 두 번 추가되는 경우를 주의하세요 (서로 다른 이웃들이 동일한 정점을 가질 수 있습니다). 루프의 시작 부분에서 방문 세트(visited set)를 확인하고 이미 방문한 경우 건너뛰십시오.
챌린지
쉬움2차원 정수 배열 adjacency(각 행은 [u, v] 간선임)와 정수 start를 입력받아, start로부터의 DFS 방문 순서를 정수 리스트로 반환하는 함수 dfs를 작성하세요.
각 간선을 추가하여 그래프를 구축하세요. 스택을 이용한 반복적 DFS를 사용합니다: 정점을 꺼내고(pop), 방문하지 않았다면 기록한 뒤 그 이웃들을 내림차순으로 정렬(reverse-sorted)하여 스택에 넣으세요. 이렇게 하면 가장 작은 정점이 먼저 처리됩니다.
반드시 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 = dfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}