99클럽 코테 스터디 4일차 TIL + DFS(C++)

문제

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

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

 

코드

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

int idx = 1; // 방문 순서
vector<int> visited(100001);
vector<int> graph[100001];

void dfs(int x) {
    visited[x] = idx++; // 정점 x의 방문 순서를 저장하고 idx를 1 증가시킴

    for (int y : graph[x]) {
        if (!visited[y])
            dfs(y);
    }
}

int main(void) {
    int N, M, R;
    cin >> N >> M >> R;

    // 1. 그래프에 정점 저장
    while (M--) {
        int u, v;
        cin >> u >> v;

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

    // 2. 각 정점의 인접 정점을 오름차순으로 정렬
    for (int i = 1; i <= N; i++)
        sort(graph[i].begin(), graph[i].end());

    // 3. dfs
    dfs(R); 

    // 4. 정점 i의 방문 순서를 출력
    for (int i = 1; i <= N; i++)
        cout << visited[i] << '\n';

    return 0;
}

 

접근 방법

깊이 우선 탐색이라는 문제 유형을 아예 알려주고 시작하는 문제라 비교적 수월하게 풀 수 있었던 것 같다.

 

1. 그래프에 정점 입력

그래프에 (u, v) 쌍으로 된 인접 정점을 입력한다.

 

2. 각 정점의 인접 정점을 오름차순으로 정렬

sort 함수를 사용한다.

 

3. 시작 정점(R)부터 DFS 호출

DFS로 탐색을 시작한다. 이때, 정점별로 방문 순서를 저장해야 하기 때문에 방문 순서를 가리키는 idx 변수를 사용한다. 정점에 방문할 때마다 visited[x] = idx++; 로 visited에 해당 정점의 방문 순서를 저장하고, idx를 1 증가시킨다.

 

4. 정점 i의 방문 순서 출력

visited를 순회하며 정점 i에 대해 해당 정점의 방문 순서를 출력한다. 이렇게 하면 dfs가 실행되지 않은 정점에 대해서는 0을 출력하게 된다.

 

회고

원래는 아래와 같이 정점의 개수(N)에 따라 graph와 visited의 크기를 동적으로 할당하는 방식으로 코드를 작성했다.

하지만 다른 사람의 풀이를 보고나서 굳이 그럴 필요가 없다는 걸 알게 됐다.

이미 문제에 N의 범위가 주어져 있기 때문에, graph와 visited를 전역 변수로 선언해 사용할 수 있었다.

고정 크기 배열을 사용하면 필요 이상의 메모리를 사용하게 된다는 단점이 있긴 하지만, dfs 호출시마다 별도의 매개변수를 전달하지 않아도 되므로 가독성 면에서는 훨씬 간결하다.

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

int idx = 1;

void dfs(int x, vector<int> &visited, vector<vector<int>> &graph) {
   // ...
}

int main(void) {
    int N, M, R;
    cin >> N >> M >> R;

    // 정점의 개수에 따라 동적으로 graph와 visited의 크기를 할당
    vector<vector<int>> graph(N + 1);
    vector<int> visited(N + 1);

    // 1. 그래프에 정점 저장
    // ...

    // 2. 각 정점의 인접 정점을 오름차순으로 정렬
    // ...

    // 3. dfs
    dfs(R, visited, graph); 

    // 4. 정점 i의 방문 순서를 출력
    // ...

    return 0;
}