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

 

1) 문제설명

백준 Online Judge 알고리즘 수업 - 깊이 우선 탐색 1

백준 Online Judge 알고리즘 수업 - 깊이 우선 탐색 1

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

24479번: 알고리즘 수업 - 깊이 우선 탐색 1

 

2) 아이디어

문제에서 오름차순으로 방문한다고 하였으므로 노드들을 입력받은 후 오름차순으로 정렬한다.

DFS대로 노드를 순회하며 방문한 곳을 체크하고 새로운 배열에 저장한다.

이후 방문한 순서대로 노드를 출력한다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;

vector<int> graph[100001];
int visited[100001] = { 0, };
int result[100001];
int cnt = 0;

void dfs(int r) {
	if (visited[r] == 1) { // 방문 한 곳이면 return
		return;
	}

	visited[r] = 1; // 방문하지 않았다면 방문했다고 표시
	cnt++;
	result[r] = cnt;

	for (int i = 0; i < graph[r].size(); i++) {
		dfs(graph[r][i]); 
	}
}
int main() {
	int n, m, r;
	scanf("%d %d %d", &n, &m, &r);
	for (int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		graph[a].push_back(b); // (1,4) (1,2) (2,3) (2,4) (3,4)
		graph[b].push_back(a); // (4,1) (2,1) (3,2) (4,2) (4,3)	
	}
	for (int i = 1; i <= n; i++) {
		sort(graph[i].begin(), graph[i].end());
	}
	dfs(r);
	for (int i = 1; i <= n; i++) {
		printf("%d\n", result[i]);
	}
	
}

입력과 출력을 cin, cout으로 하면 시간 초과가 일어난다.

scanf과 printf로 입력과 출력을 하도록 한다.