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

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

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

DFS 문제입니다.

그래프 탐색 중, DFS를 이용한 문제입니다.

시작점이 주어졌을 때, 다른 정점을 몇번만에 방문하는지를 출력해야됩니다.

 

저는 check, Cnt 배열을 이용해, check 배열에는 방문 여부를, Cnt 배열에는 방문 순서를 저장했습니다.

 

탐색을 진행하기 전에, 오름차순 방문을 위해 오름차순으로 정렬을 꼭 해줘야합니다!

 

 

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

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

using namespace std;

int N, M, R;
vector<int> connect[100001];
int check[100001];
int Cnt[100001];
int cnt = 1;

void dfs(int node){
    check[node] = 1;
    Cnt[node] = cnt++;
    for(int i = 0; i < connect[node].size(); i++){
        int x = connect[node][i];
        if(check[x] == 0){
            dfs(x);
        }
    }
}

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

 

 

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