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

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

24482번: 알고리즘 수업 - 깊이 우선 탐색 4

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

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

void dfs(int cur, int depth)
{
    visited[cur]=depth; //깊이 저장 및 방문체크
    for(int i=0; i<vec[cur].size(); i++)
    {
        int next = vec[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;
    while(M--)
    {
        int u, v;
        cin >> u >> v;
        vec[u].push_back(v); //무방향 그래프
        vec[v].push_back(u);
    }

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

    return 0;
}

 

백준 24481번과 거의 유사한 문제이다.

해당 문제는 오름차순 정렬을 필요했지만 이번 문제는 내림차순 정렬을 사용했다.

이외에는 동일하다.

기본 오름차순이기에 오름차순을 할때는 sort만 사용하면 되지만, 내림차순 일시에는 따로 사용자 정의 함수를 사용하던가, greater<>()를 사용해 내림차순으로 바꿔준다.

 

참고링크 : https://blob-thinking.tistory.com/364

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