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

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

깊이 우선 탐색의 가장 기초

그런데 입력량이 많아 시간초과에 주의할 것

1. 문제

---

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

간단 설명

깊이 우선 탐색 방법의 가장 기초 구현

노드를 방문하면서, 방문한 순서를 기록하고

마지막에 몇번째 방문했는지 출력하는 문제

2. 문제 분석

---

알고리즘

1. N, M, R을 입력받고, 연결리스트 백터의 사이즈를 조절한다
2. M개의 간선 정보를 입력받는다. 이때 무방향 간선이므로 양방향으로 삽입해준다
3. 연결리스트의 원소를 정렬해준다.(오름차순으로 방문예정이므로)
4. 노드 R부터 시작하여 DFS을 시작한다
    4-1. 현재 노드를 방문 처리한다
    4-2. 결과 배열에 이 노드가 몇번째 방문인지 기록한다
    4-3. 이 노드와 연결된 노드를 연결리스트를 통해 확인한다
    4-4. 존재하면 이 노드번호를 이용해 DFS를 호출한다 
    4-5. 연결된 모든 노드를 방문할때까지 4번을 반복한다
5. 1~N번 노드의 방문 순서를 출력한다

필요변수

노드 개수 N, 간선 개수 M, 시작 노드 N

연결 리스트를 구현할 2중 벡터 vector<vector<int>>

각 노드의 방문 여부를 기록할 visited 배열

각 노드가 몇번째 방문인지 기록할 result 배열

주의점

• 인접 정점을 오름차순으로 방문해야한다
• 입력량이 많으므로 cin, cout으로 입력받을시 시간초과에 주의할 것

3. 소스코드

ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

를 이용해 C++ cin, cout 속도를 높이는 방법도 있지만,

나는 scanf, printf를 이용했다

---

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

using namespace std;

#define MAX 100005

int N, M, R;
vector< vector<int> > graph;
int result[MAX];
int visited[MAX];
int cnt = 0;

void DFS(int now) {
	if (visited[now] == 1) return; // 이미 방문한 노드라면 종료

	visited[now] = 1;
	result[now] = ++cnt; // 몇번째 방문인지 기록해둠

	// 현재 노드와 연결된 노드를 찾아 다음 DFS 호출
	for(int i=0; i<graph[now].size(); i++)
		DFS(graph[now][i]);

	// 원복시키지 않아도 상관없음 한번 방문하면 끝임. 
	// visited[now] = 0;

}

int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	scanf("%d %d %d", &N, &M, &R);
	// cin >> N >> M >> R;

	graph.resize(N + 1); // 연결리스트 벡터를 N+1로 리사이즈

	// 1. 입력
	for (int i = 0; i < M; i++) {
		int start, end;
		scanf("%d %d", &start, &end);
		// cin >> start >> end;

		graph[start].push_back(end);
		graph[end].push_back(start);
	}

	// 2. 연결 리스트의 원소를 정렬
	for (int i = 1; i <= N; i++) {
		sort(graph[i].begin(), graph[i].end());
	}

	// 3. 시작 원소 R부터 DFS 시작
	DFS(R);

	// 4. result 배열에 저장된 숫자 출력
	for (int i = 1; i <= N; i++) {
		printf("%d\n", result[i]);
		// cout << result[i] << endl;
	}

	return 0;
}