문제 개요
N개의 정점과 M개의 간선으로 이루어진 연결 그래프가 주어졌을 때, 1번 정점에서 시작하는 깊이 우선 탐색(DFS) 순회 결과 중 사전순으로 가장 작은(lexicographically smallest) 순서를 출력하는 것이 목표입니다.
정점의 번호는 1부터 N까지 차례대로 매겨집니다.
예시
입력: N = 5, M = 5 edge(1, 4, arr) edge(3, 4, arr) edge(5, 4, arr) edge(3, 2, arr) edge(1, 5, arr) edge(1, 2, arr) edge(3, 5, arr) edge(1, 3, arr) 출력: 1 2 3 4 5
접근 방법
일반적인 DFS를 곧바로 수행하는 대신, 먼저 각 정점의 인접 리스트를 오름차순으로 정렬합니다. 이렇게 하면 DFS 탐색 과정에서 항상 번호가 가장 작은 인접 정점을 우선적으로 방문하게 됩니다. 따라서 정렬 후에는 평범한 DFS만 수행해도 자연스럽게 사전순으로 가장 작은 순회 결과를 얻을 수 있습니다.
핵심 아이디어를 정리하면 다음과 같습니다.
- 각 정점의 인접 리스트를 오름차순으로 정렬한다.
- 1번 정점부터 DFS를 시작하고, 방문 여부는 별도의 배열로 관리한다.
- 아직 방문하지 않은 인접 정점 중 번호가 가장 작은 정점부터 재귀적으로 탐색한다.
아래는 이 알고리즘의 C++ 구현 코드입니다.
알고리즘
시작
Step 1 -> 함수 void lexo(vector<int>* arr, int n) 선언
bool check[n + 1] = { 0 } 선언
int i = 0; i < n; i++ 반복
sort(arr[i].begin(), arr[i].end()) 호출
int i = 1; i < n; i++ 반복
IF !check[i]
graph(arr, i, n, check) 호출
End
End
Step 2 -> 함수 void edge(int u, int v, vector<int>* arr) 선언
ar[u].push_back(v) 호출
ar[v].push_back(u) 호출
Step 3 -> 함수 void graph(vector<int>* arr, int src, int n, bool* check) 선언, src 출력
check[src] = true 설정
int i = 0; i < arr[src].size(); i++ 반복
IF !check[arr[src][i]]
graph(arr, arr[src][i], n, check) 호출
End
End
Step 4 -> main() 함수
int n = 5, m = 5 선언
STL vector<int> arr[n + 1] 사용
edges(1, 4, arr), edges(3, 4, arr)... 호출
lexo(arr, n) 호출
종료
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
// 간선 삽입용 함수
void edge(int u, int v, vector<int>* arr){
arr[u].push_back(v);
arr[v].push_back(u);
}
// DFS 그래프 순회 함수
void graph(vector<int>* arr, int src, int n, bool* check){
cout << src << " ";
check[src] = true;
for (int i = 0; i < arr[src].size(); i++){
if (!check[arr[src][i]])
graph(arr, arr[src][i], n, check);
}
}
// 사전순 최소 DFS를 위한 함수
void lexo(vector<int>* arr, int n){
bool check[n + 1] = { 0 };
for (int i = 0; i < n; i++)
sort(arr[i].begin(), arr[i].end());
for (int i = 1; i < n; i++){
if (!check[i])
graph(arr, i, n, check);
}
}
int main(){
int n = 5, m = 5;
vector<int> arr[n + 1];
// 간선 삽입
edge(1, 4, arr);
edge(3, 4, arr);
edge(5, 4, arr);
edge(3, 2, arr);
edge(1, 5, arr);
edge(1, 2, arr);
edge(3, 5, arr);
edge(1, 3, arr);
// lexo 함수 호출
lexo(arr, n);
return 0;
}
코드 설명
- edge(): 무방향 그래프이므로 두 정점 u와 v를 서로의 인접 리스트에 추가합니다.
- graph(): 현재 정점을 출력하고 방문 표시를 한 뒤, 아직 방문하지 않은 인접 정점에 대해 재귀적으로 DFS를 수행합니다.
- lexo(): 모든 정점의 인접 리스트를 정렬한 후, 방문하지 않은 정점에서 DFS 탐색을 시작합니다.
실행 결과
위 프로그램을 실행하면 다음과 같은 출력이 생성됩니다.
1 2 3 4 5
시간 복잡도
인접 리스트를 정렬하는 데 O(M log M), DFS 순회에 O(N + M)이 소요되므로 전체 시간 복잡도는 O(M log M)입니다. 간선의 개수가 많지 않다면 충분히 효율적으로 동작합니다.