[BOJ] 단계별로 풀어보기 24479 깊이 우선 탐색 1 C++ 문제풀이 & 소스코드

INFO

난이도 : SILVER2

유형 : Graph DFS

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

---

SOLVE

문제에서 주어진 조건대로 각 노드를 오름차순으로 DFS 탐색을 해주면 되는 간단한 그래프 문제이다. 

단 cin, cout 속도를 최적화해 주는 코드를 반드시 명시해 주어야 한다. 그렇지 않으면 시간초과가 발생한다. 

    cin.tie(0);
    ios_base::sync_with_stdio(0);

 

인접 리스트 방식으로 간선 정보를 입력받는다. 

vector<int> adj_list[200001];
    for (int i = 1; i <= m; i ++) {
        cin >> node1 >> node2;
        adj_list[node1].push_back(node2);
        adj_list[node2].push_back(node1);
    }

 

문제 조건에서 인접 정점을 오름차순으로 탐색해야 된다는 조건이 있었기에 각 노드에 저장된 인접 정점을 sort 함수를 사용해 오름차로 정렬한 뒤, 정점 r에서 dfs 탐색을 시작한다. 

    // 탐색 순서를 sort
    for (int i = 1; i <= n; i++) {
        sort(adj_list[i].begin(), adj_list[i].end());
    }
    
    dfs(r);

 

dfs 로직은 크게 다를건 없는데

해당 정점을 몇 번째로 탐색했는지 출력해야 하기에 정점을 탐색할 때마다 cnt 변수값을 증가시켜 ans 배열에 기록해 주기만 하면 된다.

bool visited[200001];
int ans[200001];
vector<int> adj_list[200001];
int cnt = 0;

void dfs(int r) {
    
    if (visited[r]) return;
    visited[r] = true;
    cnt++;
    ans[r] = cnt;
    for (int i = 0; i < adj_list[r].size(); i++) {
        dfs(adj_list[r][i]);
    }
}

---

CODE

https://github.com/novvvv/PS/blob/main/BOJ/2025/C%2B%2B/24479.cpp

PS/BOJ/2025/C++/24479.cpp at main · novvvv/PS

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

bool visited[200001];
int ans[200001];
vector<int> adj_list[200001];
int cnt = 0;

void dfs(int r) {
    
    if (visited[r]) return;
    visited[r] = true;
    cnt++;
    ans[r] = cnt;
    for (int i = 0; i < adj_list[r].size(); i++) {
        dfs(adj_list[r][i]);
    }
}

int main() {
    
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    
    int n, m, r; // 정점 수 , 간선 수, 시작 정점
    cin >> n >> m >> r;

    int node1, node2;
    
    for (int i = 1; i <= m; i ++) {
        cin >> node1 >> node2;
        adj_list[node1].push_back(node2);
        adj_list[node2].push_back(node1);
    }
    
    // 탐색 순서를 sort
    for (int i = 1; i <= n; i++) {
        sort(adj_list[i].begin(), adj_list[i].end());
    }
    
    dfs(r);
    
    for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
    
}

// N개 정점 (5 <= N <= 100,000) , M개 간선 (1 <= M <= 200,000)
// 정점 R에서 시작해 깊이 우선 탐색으로 노드를 방문한다.
// 노드의 방문 순서를 출력하시오.

// 간선 정보 U v
// 정점 u 정점 v 가중치 1 양방향 간선