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

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

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

DFS를 이용해 방문 노드의 깊이를 구하는 문제입니다.

방문 노드의 순서가 아닌, 깊이를 방문하는 것이기에, 노드를 방문할 때마다, 1를 증가해 값을 입력하면 안됩니다.

 

또한, 인접 노드는 내림차순으로 방문하기에, 정렬 기준을 세우거나, reverse를 사용해 탐색을 해야했습니다.

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second

using namespace std;

int N, M, R;
vector<int> connect[100001];
int check[100001];

bool cmp(int x, int y){
    if(x > y) return true;
    else return false;
}

void dfs(int x, int cnt){
    check[x] = cnt;
    for(int i = 0 ; i < connect[x].size(); i++){
        int xx = connect[x][i];
        if(check[xx] != -1) continue;
        dfs(xx, cnt + 1);
    }
}

void solve(){
    for(int i = 1; i <= N; i++){
        sort(connect[i].begin(), connect[i].end(), cmp);
    }
    memset(check, -1, sizeof(check));
    dfs(R, 0);
    for(int i = 1; i <= N; i++){
        cout << check[i] << "\n";
    }
}

int main() {
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M >> R;
    for(int i = 1; i <= M; i++){
        int x, y;
        cin >> x >> y;
        connect[x].push_back(y);
        connect[y].push_back(x);
    }
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요