[백준] 24479번 C++ 문제풀이

1. 탐색 순서: 특정 경로를 따라 끝까지 탐색한 뒤, 다른 경로로 전환.
2. 자료구조: 재귀(스택 기반 호출 스택) 또는 명시적으로 스택을 활용.
3. 시간복잡도: O(V+E)
4. 적용 사례: 경로 찾기, 사이클 탐지, 연결 요소 확인, 위상 정렬 등.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include<array>

using namespace std;


vector<int> graph[200000];
array<int, 200'001> visited{};

int cnt{};

void dfs(int node) {
    if (visited[node]) return;
    
    visited[node] = ++cnt;

    for (int i = 0; i < graph[node].size(); ++i) {
        int y = graph[node][i];
        dfs(y);
    }

}


int main() {
    int n, m, r;
    cin >> n >> m >> r;

    // 그래프 입력
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;

        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    // 인접 리스트를 오름차순으로 정렬
    for (int i = 1; i <= n; ++i) {
        sort(graph[i].begin(), graph[i].end());
    }

    // DFS 수행
    dfs(r);

    // 방문 순서 출력
    for (int i = 1; i <= n; ++i) {
        cout << visited[i] << '\n';
    }

}

dfs는 재귀와 스택으로 푸는 방식이 있는데 구현에 있어서 재귀가 조금 더 간편하다.

따라서 이번에는 재귀를 이용해서 풀어보았다.