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

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

24480번: 알고리즘 수업 - 깊이 우선 탐색 2

DFS를 사용하는 문제입니다. 내림차순으로 탐색하는 것을 주의해야 했습니다.

 

DFS를 이용해 그래프 탐색을 할 때, 노드 방문 순서를 출력하는 문제입니다.

노드를 방문할 때, 인접 정점은 내림차순으로 방문한다는 것이 중요했습니다.

 

DFS 코드는 재귀 함수를 이용했습니다.

 

DFS를 탐색하기 전에, 노드를 정렬해야했습니다. 

sort -> reverse를 사용하는 방법도 있겠지만, 정렬 기준을 정해 정렬해주는 방법을 사용해줬습니다.

 

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

 return 값이 true 라면 값을 바꾸지 않고, false라면 값을 바꾸라는 뜻입니다.

 

 

 

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

#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];
int cnt = 1;

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

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

void solve(){
    for(int i = 1; i <= N; i++){
        sort(connect[i].begin(), connect[i].end(), cmp);
    }
    dfs(R);
    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;
}

 

 

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