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

https://www.acmicpc.net/problem/24479

단계별로 풀어보기

27단계(그래프와 순회) 1번째

 

 

 

PS에서 정말 많이 나오는 그래프다. 그래프, DFS, BFS 등을 설명하기에는 끝도 없으므로 그래프 문제에서 문제풀이에 대한 설명이 아닌 개념에 대한 설명은 최대한 생략한다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m, r, x= 1;
  
  cin >> n >> m >> r;
  
  vector adj(n+1, vector<int>());
  vector<int> visited(n+1);
  
  while(m--){
    int u, v;
    
    cin >> u >> v;
    
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  
  for(int i=1;i<=n;i++)  sort(adj[i].begin(), adj[i].end());
  
  auto dfs= [&](auto self, int now) -> void {
    visited[now]= x++;
    
    for(int next:adj[now]){
      if(visited[next])  continue;
      
      self(self, next);
    }
  };
  
  dfs(dfs, r);
  
  for(int i=1;i<=n;i++)  cout << visited[i] << "\n";
  
  return 0;
}