[C++] 백준 24479번 - 알고리즘 수업(깊이 우선 탐색 1)

 

문제 24479번

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

 

모든 간선의 쌍을 벡터에 넣어준다. 이때 양방향 간선이기 때문에 반대인 경우도 같이 넣어준다. 그리고 인접 정점은 오름차순으로 방문하기 때문에 sort로 정렬해준다.

 

깊이 우선 탐색을 하기 위해 따로 함수로 만들어주었다. 만약 방문한 점이면 빠져나와주고 아니라면 방문 표시를 한 후 해당 정점을 결과 배열에 넣어준다. 그리고 해당 정점과 연결된 점을 차례로 방문해준다.

 

그렇게 다 방문하면 result를 출력해준다.

 

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

vector <int> graph[100001];
bool visited[100001];
int result[100001];
int cnt = 0;

void dfs(int r) {
	if (visited[r] == true) {	//방문함
		return;
	}
	visited[r] = true;
	cnt++;
	result[r] = cnt;
	for (int i = 0; i < graph[r].size(); i++) {
		dfs(graph[r][i]);
	}
}

int main() {
	int n, m, r;
	cin >> n >> m >> r;
	for (int i = 0; i < m; i++) {	//간선
		int u, v;
		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());	//오름차순
	}
	dfs(r);
	for (int i = 1; i <= n; i++) {
		cout << result[i] << '\n';
	}

	return 0;
}