백준 24479_알고리즘 수업 - 깊이 우선 탐색 1 문제풀이 in C++

2022년 05월 23일 in Devlog on Algorithm

1. 문제 URL
2. 문제 요구사항
3. 접근 방법
4. 풀이 순서
5. 소스코드
6. 문제 풀이 결과

문제 URL

---

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

문제 요구사항

---

• 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인 양방향 간선을 나타낸다.

접근 방법

---

• 문제에서 착하게 의사 코드를 제시 해주고 있다. 문제에서 주어진 의사 코드를 구현하면 된다. 나는 DFS의 기본 개념을 까먹은 거 같아 해당 문제를 풀어봤다.

풀이 순서

---

1. N(정점의 개수), M(간선의 개수), R(시작 정점)을 입력 받는다.
2. 이후, M(간선의 개수)만큼 반복하여 간선 정보를 입력 받는다.
3. 나는 간선 정보를 vector<vector>로 해서 받았다.
4. 해당 간선 정보의 각 인덱스를 오름차순으로 정렬한다.
5. DFS 수행
   • 이때, 매개변수로 받게 되는 정점은 check 하여, 중복으로 올 수 없게 한다.
   • 또, 해당 방문 정점을 기록해야 하므로, 전역변수 result에 임의의 가중치 변수 값을 넣어 순서를 기록한다.
6. 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 checkedNode[100001];
int k = 1;
void input() {
	cin >> N >> M >> R;

	memset(checkedNode, false, sizeof(checkedNode));

	for (int i = 0; i < M; i++) {
		int a, b;
		cin >> a >> b;

		v[a].push_back(b);
		v[b].push_back(a);
	}

	for (int i = 1; i <= N; i++) {
		sort(v[i].begin(), v[i].end());
	}
}

void DFS(int start_idx) {
	checkedNode[start_idx] = true;
	result[start_idx] = k;
	for (int i = 0; i < v[start_idx].size(); i++) {
		if (checkedNode[v[start_idx][i]] == false) {
			k++;
			DFS(v[start_idx][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();
	DFS(R);
	output();

	return 0;
} 

문제 풀이 결과

---