[백준 24481번] 알고리즘 수업 - 깊이 우선 탐색 3 (C++)

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

24481번: 알고리즘 수업 - 깊이 우선 탐색 3

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, R;
vector<int>v[100001];
int visited[100001];

void dfs(int cur, int depth)
{
    visited[cur] = depth; //깊이 저장
    for(int i=0; i<v[cur].size(); i++)
    {
        int next = v[cur][i];
        if(visited[next]!=-1) continue;
        dfs(next, depth+1);
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> M >> R;
    for(int i=1; i<=M; i++)
    {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y); //무방향 그래프
        v[y].push_back(x);
    }

    for(int i=1; i<=N; i++) sort(v[i].begin(), v[i].end()); //오름차순 정렬
    memset(visited, -1, sizeof(visited));
    dfs(R, 0);
    for(int i=1; i<=N; i++) cout << visited[i] << "\n";

    return 0;
}

 

기본적인 dfs 문제에 오름차순 정렬이 추가된 문제이다.

해당 문제에서 인접 정점에 대해서 오름차순으로 방문한다고 했기에 이를 위해 dfs 탐색 전 입력받은 값에 대해 오름차순으로 정렬을 우선 시행한다.

 

이후 dfs 탐색을 통해 다음 위치와 늘어난 깊이 (+1)을 넘겨주어 깊이를 저장하고 이를 출력해준다.