백준 24479번 [알고리즘 수업 - 깊이 우선 탐색 1](C++) -yes6686- 티스토리

백준 문제 풀이: 24479 [알고리즘 수업 - 깊이 우선 탐색 1]

---

문제 링크: https://www.acmicpc.net/problem/24479

문제 설명:

양방향 그래프가 주어질 때, 주어진 시작 노드 r에서 깊이 우선 탐색(DFS)을 수행하고 각 노드가 탐색된 순서를 출력하는 문제입니다.

다음 조건이 적용됩니다:

• DFS는 노드의 번호가 작은 순서대로 방문합니다.
• 방문하지 않은 노드가 있을 경우, 해당 노드는 0으로 출력됩니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector graph[100001]; // 그래프의 인접 리스트
int visited[100001];       // 방문 여부를 저장
int order[100001];         // 방문 순서를 저장
int depth = 1;             // 방문 순서 기록을 위한 변수

// 깊이 우선 탐색 함수
void dfs(int node) {
    visited[node] = 1;        // 현재 노드를 방문 처리
    order[node] = depth++;    // 현재 노드의 방문 순서 저장
    for (int neighbor : graph[node]) { // 인접 노드 순회
        if (!visited[neighbor]) {      // 방문하지 않은 노드만 탐색
            dfs(neighbor);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    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(r);

    // 결과 출력
    for (int i = 1; i <= n; i++) {
        cout << order[i] << '\n';
    }

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 깊이 우선 탐색(DFS)을 통해 그래프를 순회하며 방문 순서를 기록합니다. DFS의 재귀 구조와 작은 번호부터 방문하는 특성을 활용합니다.
• 구현 세부사항:
  • 각 노드의 인접 리스트를 정렬하여 DFS가 노드 번호가 작은 순서대로 방문하도록 합니다.
  • DFS 호출 시, 방문 여부를 확인하여 중복 방문을 방지합니다.
• 시간 복잡도 분석:
  • 그래프의 정렬: O(E log E), 여기서 E는 간선 수
  • DFS 수행: O(V + E), 여기서 V는 노드 수
  전체 시간 복잡도는 O(E log E + V + E)로, E가 지배적일 경우 약 O(E log E)입니다.

---

결과

각 노드의 방문 순서가 정확히 출력됩니다. DFS의 동작 원리와 노드 정렬의 중요성을 활용한 풀이입니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!