[백준 24479] 알고리즘 수업 - 깊이 우선 탐색 1

백준 문제 참고 링크

공유 소스 보기 (acmicpc.net)

공유 소스 보기

 

수도 코드(pseudo-code) : 의사 코드

dfs(V, E, R) {  # V : 정점 집합, E : 간선 집합, R : 시작 정점
    visited[R] <- YES;  # 시작 정점 R을 방문 했다고 표시한다.
    for each x ∈ E(R)  # E(R) : 정점 R의 인접 정점 집합.(정점 번호를 내림차순으로 방문한다)
        if (visited[x] = NO) then dfs(V, E, x);
}

 

재귀로 구현한 dfs1

스택으로 구현한 dfs2

#include<bits/stdc++.h>
#define fio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

using namespace std;

int n,m,s,a,b,idx=1;
vector<int> adj[100'005]; //인접리스트
int answer[100'005];
bool visited[100'005];

void dfs1(int cur){
    visited[cur] = true;
    answer[cur] = idx++;
    for(int x : adj[cur]){
        if(!visited[x]) dfs1(x);
    }
}

void dfs2(){
    stack<int> S;
    S.push(s);
    while (!S.empty()){
        int cur = S.top();
        S.pop();
        if(visited[cur]) continue;
        visited[cur] = true;
        answer[cur] = idx++;
        for(int nxt : adj[cur]){
            if(!visited[nxt]) S.push(nxt);
        }
    }
}

int main(){
    fio;
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++){
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 1; i <= n; i++){
        sort(adj[i].begin(), adj[i].end(), greater());
    }

    dfs2();
    for (int i = 1; i <= n; ++i) {
        cout << answer[i] << '\n';
    }
    return 0;
}