깊이 우선 탐색 1 [C++]

문제 링크: https://www.acmicpc.net/problem/24479

난이도: ⚪⚪

문제 설명

문제 접근

1. 문제에서 제공한 DFS의 의사코드를 이용한다.
2. 가중치는 모두 1이고 무방향 그래프라는 것에 유의한다.
3. 인접 정점은 오름차순으로 방문하기때문에 리스트를 정렬해야 한다.
   
   

제출 코드

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

vector<int> graph[100001];
int visited_seq[100001];
bool visited[100001];

// 방문 순서
int seq = 1;

// DFS 구현
void DFS(int node)
{
	visited[node] = true;
    // 방문하는 node를 인덱스로 하는 visited_seq 배열에 seq값을 넣어주고 값을 증가시킨다.
	visited_seq[node] = seq;
	seq++;
	for (int i = 0; i < graph[node].size(); i++)
		if (!visited[graph[node][i]])
			DFS(graph[node][i]);
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N, M, R;
	cin >> N >> M >> R;
	
    // 무방향 그래프이기 때문에 양쪽 노드에 추가한다.
	for (int i = 0; i < M; i++)
	{
		int node1, node2;
		cin >> node1 >> node2;
		graph[node1].push_back(node2);
		graph[node2].push_back(node1);
	}
    
    // 오름차순 정렬.
	for (int i = 0; i < N + 1; i++)
		sort(graph[i].begin(), graph[i].end());
	
	DFS(R);
	
	for (int i = 1; i < N + 1; i++)
		cout << visited_seq[i] << '\n';
	
	return 0;
}

결과