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

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

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

DFS를 이용해 노드 깊이를 구하는 문제였습니다.

방문 순서가 아닌, 방문 깊이이기 때문에, 정점을 방문할 때마다 1씩 증가해서 넣으면 안됩니다.

 

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);
    }
}

check 배열의 값을 전부 -1로 초기화한 뒤 시작했습니다.

 

 

 

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

#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];


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());
    }
    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;
}

 

 

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