자료구조 및 알고리즘/백준
[백준 24479] 알고리즘 수업 - 깊이 우선 탐색 1
아기사우르스
2023. 3. 28. 15:43
728x90
백준 문제 참고 링크
수도 코드(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;
}
728x90