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

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

출력이 노드의 순서대로 출력함과 동시에 방문 순서를 적는 형식이다.

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> list;
vector<int> visitedOrder;
int order = 1;

void dfs(int start)
{
	visitedOrder[start] = order;

	for (int i = 0; i < list[start].size(); i++)
	{
		int next = list[start].at(i);

		if (!visitedOrder[next])
		{
			order++;
			dfs(next);
		}	
	}
}

int main()
{
	int N, M, R = 0;

	cin >> N >> M >> R;

	list = vector<vector<int>>(N + 1);
	visitedOrder = vector<int>(N + 1, 0);

	for (int i = 0; i < M; i++)
	{
		int u, v;

		cin >> u >> v;

		list[u].push_back(v);
		list[v].push_back(u);
	}

	for (int i = 0; i < N + 1; i++)
		sort(list[i].begin(), list[i].end());
	
	dfs(R);

	for (int i = 1; i < N + 1; i++)
		cout << visitedOrder[i] << '\n';

	return 0;
}

기존 DFS문제처럼 bool로 방문했는지 확인하는 것이 아닌 방문 순서를 저장할 수 있는 int로 확인을 하였다.

양방향 간선이므로 서로의 list에 정점을 넣어주었고, sort 진행 후 방문 순서를 확인하였다.

 

시간 초과가 의외의 복병이였는데 c++에서 cout 출력을 할 때 endl을 사용하면 버퍼를 비우게 되는데, 그 때 시간이 많이 소요된다고 한다.

'\n' 으로 고쳐서 제출했더니 시간초과가 발생하지 않았다.