[DFS & BFS] 백준 : 24480_알고리즘 수업 - 깊이 우선 탐색 2

[inseonyun]

Source URL : https://www.acmicpc.net/problem/24480

[inseonyun]

문제 요구사항

• N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다.
• 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다.
• 인접 정점은 내림차순으로 방문한다.
• 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.
  • 첫째 줄부터 N개의 줄에 정수를 한 개씩 출력한다.
  • i번째 줄에는 정점 i의 방문 순서를 출력한다.
  • 시작 정점의 방문 순서는 1이다.
  • 시작 정점에서 방문할 수 없는 경우 0을 출력한다.
• 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.
• 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다.

접근 방법

• 24479 문제에서 정렬을 내림차순으로 하면 되는 문제이다.
• 문제에서 착하게 의사 코드를 제시 해주고 있다. 문제에서 주어진 의사 코드를 구현하면 된다. 나는 DFS의 기본 개념을 까먹은 거 같아 해당 문제를 풀어봤다.

풀이 순서

1. N(정점의 개수), M(간선의 개수), R(시작 정점)을 입력 받는다.
2. 이후, M(간선의 개수)만큼 반복하여 간선 정보를 입력 받는다.
3. 나는 간선 정보를 vector<vector>로 해서 받았다.
4. 해당 간선 정보의 각 인덱스를 내림차순으로 정렬한다.
5. DFS 수행
   • 이때, 매개변수로 받게 되는 정점은 check 하여, 중복으로 올 수 없게 한다.
   • 또, 해당 방문 정점을 기록해야 하므로, 전역변수 result에 임의의 가중치 변수 값을 넣어 순서를 기록한다.
6. N(정점의 개수)만큼 result의 각 value 출력

[inseonyun]

[문제 풀이 결과]