문제

문제 링크 : https://www.acmicpc.net/problem/24480 (단계별로 풀어보기: 그래프와 순회)

문제 풀이

해당 문제는 baekjoon 24479 다음 문제로 24479 문제와 인접 정점을 방문할때 내림차순 으로 방문한다 부분만 차이가 있다. 따라서 전체 문제풀이는 다음을 참고하면 좋을 것 같다.
https://velog.io/@jeus/Baekjoon-24479-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%88%98%EC%97%85-%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-1
이전 문제와 달라진 점은 인접 정점 방문 순서가 오름차순에서 내림차순으로 바뀌었으므로 벡터를 정렬할 때 오름차순이 아닌 내림차순으로 정렬하도록 코드를 수정했다. sort함수를 이용하여 정렬하였으므로 함수 인자로 greater()를 주어 내림차순으로 정렬하였고, less<>() 형식으로 주면 기본값인 오름차순으로 정렬되며, compare 함수를 구현하여 인자로 넣어줘도 구현이 가능하다.

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

vector <vector<int>> graph;
vector <int> visited;
vector <int> sequence;
int N, M, R, Seq;

void input();
void dfs(int n);
void sol();

int main()
{   
  fastio;
  input();
  sol();
  return 0;
}

void input()
{
  cin >> N >> M >> R;
  graph.resize(N+1);
  visited.resize(N+1);
  sequence.resize(N+1);
  int u,v;
  for(int i=0; i<M; i++){
      cin >> u >> v;
      graph[u].push_back(v);
      graph[v].push_back(u);
  }
  for(int i=1; i<=N; i++) sort(graph[i].begin(), graph[i].end(), greater<int>());
}

void dfs(int n)
{
  sequence[n] = ++Seq;
  visited[n] = 1;
  int graphsize = graph[n].size(), v;
  for(int i=0; i<graphsize; i++){
      v = graph[n][i];
      if(visited[v]==0) dfs(v);
  }
}

void sol()
{
  dfs(R);
  for(int i=1; i<N+1; i++)    printf("%d\n",sequence[i]);
}