백준 24480_알고리즘 수업 - 깊이 우선 탐색 2 문제풀이 in C++
문제 URL
https://www.acmicpc.net/problem/24480
문제 요구사항
- 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의 기본 개념을 까먹은 거 같아 해당 문제를 풀어봤다.
풀이 순서
- N(정점의 개수), M(간선의 개수), R(시작 정점)을 입력 받는다.
- 이후, M(간선의 개수)만큼 반복하여 간선 정보를 입력 받는다.
- 나는 간선 정보를 vector<vector
>로 해서 받았다. - 해당 간선 정보의 각 인덱스를 내림차순으로 정렬한다.
- DFS 수행
- 이때, 매개변수로 받게 되는 정점은 check 하여, 중복으로 올 수 없게 한다.
- 또, 해당 방문 정점을 기록해야 하므로, 전역변수 result에 임의의 가중치 변수 값을 넣어 순서를 기록한다.
- N(정점의 개수)만큼 result의 각 value 출력
소스코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int N, M, R;
vector<vector<int>> v(100001, vector<int>());
vector<int> result(100001, 0);
bool check[100001];
int cnt = 1;
void input() {
// 정점의 개수, 간선의 개수, 시작 정점 입력 받음
cin >> N >> M >> R;
// check 배열 초기화
memset(check, false, sizeof(check));
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
}
void sortingDesc() {
// v 배열 각 행 내림차순 정렬
for (int i = 1; i <= N; i++) {
sort(v[i].begin(), v[i].end(), greater<>());
}
}
void DFS(int startX) {
check[startX] = true;
result[startX] = cnt;
for (int i = 0; i < v[startX].size(); i++) {
if (check[v[startX][i]] == false) {
cnt++;
DFS(v[startX][i]);
}
}
}
void output() {
for (int i = 1; i <= N; i++) {
cout << result[i] << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
sortingDesc();
DFS(R);
output();
return 0;
}
문제 풀이 결과
