[99클럽/코딩테스트 챌린지/C++] 깊이 우선 탐색(DFS)와 방문 순서 기록을 통한 그래프 탐색

오늘은 깊이 우선 탐색(DFS)을 통해 그래프의 방문 순서를 기록하는 방법을 배웠습니다. DFS는 재귀 호출을 통해 그래프의 노드를 탐색하며, 방문 순서까지 기록하는 방식으로 응용할 수 있습니다. 특히 인접 리스트를 사용한 오름차순 탐색과 양방향 그래프 처리가 중요한 포인트였습니다.

문제 링크 : 

https://www.acmicpc.net/problem/24479

문제 접근 과정

1, 문제 분석과 그래프 구조 선택

• 주어진 그래프는 무방향 그래프로, 양방향 간선이 존재하기 때문에 각 간선을 양쪽 모두에 추가해야 합니다.
• 정점과 간선의 개수가 크기 때문에, 인접 리스트를 사용해 그래프를 구현하였습니다. 인접 행렬 방식은 메모리와 속도에서 비효율적이므로 인접 리스트가 더 적합했습니다.

2, DFS 탐색 순서와 오름차순 방문

• DFS는 재귀적으로 각 정점을 탐색하며, 해당 정점의 인접 정점을 순서대로 방문해야 합니다. 문제에서 요구한 오름차순 방문을 만족하기 위해 모든 인접 정점 리스트를 정렬했습니다.
• visited 배열을 사용해 방문 순서를 기록하고, 방문한 순서대로 증가하는 값을 저장하여, 탐색 완료 후 모든 정점의 방문 순서를 출력할 수 있도록 하였습니다.

3, 방문 순서 출력과 예외 처리

• 탐색이 끝난 후에는 모든 정점을 순회하며 visited 배열을 확인하여, 방문 순서대로 각 정점을 출력합니다.
• DFS로 시작 정점에서 도달할 수 없는 정점은 visited 배열이 초기값(0)을 유지하므로, 도달 불가능한 정점은 0으로 표시됩니다.

코드 풀이

아래는 문제 해결을 위한 최종 코드입니다:

// ConsoleApplication1.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

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

using namespace std;

vector<vector<int>> map;
int visited[100005];
int N, M, R;
int order = 1;
void dfs(int current)
{
    // 현재 방문한 정점에서 order 값을 증가 시켜서 저장한다.
    visited[current] = order++;
    for (auto next : map[current])
    {
        if (visited[next]) continue;// 이미 방문한 정점이면 다음 정점
        dfs(next);// 현재 인접한 정점을 방문
    }
}

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

    std::cin >> N >> M >> R;
    // 인접 리스트(vector<vector<int>>)로 초기화
    map = vector<vector<int>>(N + 1);
    for(int i = 0; i < M; i++)
    {
        int a, b;
        std::cin >> a >> b;
        map[a].push_back(b);// 해당 a 값에 vector에 b 값을 추가
        map[b].push_back(a);// 무방향 간선이므로 b에도 a 값 추가
    }
    // 모든 인접 정접들은 정렬
    for(int i = 1; i <= N; i++)
    {
        sort(map[i].begin(), map[i].end());
    }
    // Dfs 시작
    dfs(R);
    // 모든 정점을 방문 했으므로 각 정점별 visited 방문 순서를 출력
    for (int i = 1; i <= N; i++)
    {
        std::cout << visited[i] << "\n";
    }
    return 0;
}

배운 점과 결론

이번 문제를 통해 DFS를 사용한 그래프 탐색에서 방문 순서를 기록하는 방법을 익힐 수 있었습니다.

 

1, 인접 리스트 사용의 효율성

• 인접 리스트를 사용하면 메모리를 아낄 수 있고, 큰 그래프에서도 빠르게 탐색할 수 있습니다. 특히 노드가 많고 간선이 드문 상황에서 유리했습니다.

2, 양방향 그래프 구현과 오름차순 정렬

• 양방향 간선은 간선을 양쪽 정점에 모두 추가하여 처리하였고, 문제의 조건에 맞게 인접 리스트를 오름차순으로 정렬하여 탐색 순서를 맞출 수 있었습니다.

3, 방문 순서 기록과 출력 형식의 중요성

• DFS 탐색 중 각 정점에 order 값을 저장하여 방문 순서를 기록하였고, 미방문 정점은 0으로 출력해 그래프의 연결 여부를 잘 표현할 수 있었습니다.

결론

이 문제를 통해 DFS를 사용해 방문 순서를 기록하는 응용 방법과, 탐색 조건을 구현하기 위한 인접 리스트와 정렬 방식을 배웠습니다. 앞으로도 그래프 탐색 문제에서 조건에 맞는 구조와 방문 기록 방법을 더 잘 활용할 수 있도록 해야겠다고 느꼈습니다.