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

백준 온라인 저지(BOJ) 24479번 알고리즘 수업 - 깊이 우선 탐색 1
https://www.acmicpc.net/problem/24479

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

* 사용언어 : C언어, C++
 

1. 문제

graph 를 DFS(깊이 우선 탐색)으로 탐색할 때

1번 정점부터 N번 정점까지 방문한 순서를 출력

(인접 정점은 오름차순으로 방문)
 

2. 풀이

재귀적 접근을 활용하는 DFS 를 구현하여 풀면 됩니다.
 
DFS 에 대한 설명과 구현 방법은 구글링하면 쉽게 찾아볼 수 있으므로

이 게시글에는 굳이 작성하지 않겠습니다.
 
대신 문제를 풀면서 고생했던 부분을 정리해보았습니다.
 

1) 메모리 제한 (512MB)

Graph 탐색을 위해 인접 노드를 표현하는 방식이 크게 2가지가 있는데

하나는 인접 배열이고 하나는 인접 리스트 방식입니다.
 
처음에 별 생각없이 손에 익은 인접 배열로 구현을 해봤는데

전역 변수로 선언했음에도 Visual Studio 에서부터 동작이 안됐습니다.

마침 문제에도 메모리 제한이 있길래(512MB) 사용한 메모리를 계산해봤습니다.
 
문제 상 node 의 최대 개수는 100,000개 이므로 이를 인접 배열(2차원)로 만들면

4(int 4bytes) * 100,000 * 100,000 == 400억 Bytes == 약 37GB 가 됩니다.
 
512MB 제한인데 이런 방식으로 구현이 가능할리가 없었고

메모리 사용을 최소화하기 위해 인접 리스트 방식을 사용하게 됐습니다.
 

2) 시간 제한 (1초)

c언어로 이 부분을 해결하기 위해서 시간을 정말 많이 사용했습니다.
 
개인적으로 STL 을 사용하지 않고 직접 구현하는 방식을 선호하는데

직접 구현하는 방식으로는 어떻게 해도 91% 시간 초과를 통과할 수가 없었습니다.

(리스트에 insert 할 때 오름차순으로 넣기, head 뒤에 바로 insert 하고 다 넣으면 한 번만 정렬하기, input 들을 전체 정렬한 후 리스트에 넣기 등등) 

결국 구글링을 결과를 참고해서 <vector> 와 <algorithm> STL 을 사용하여 풀었습니다.

 

graph 공부를 하려고 [단계 별로 풀어보기] 중 [그래프와 순회] 에서 제일 윗 문제를 시도해본건데

계획과 다르게 DFS 가 아닌 리스트, 정렬, 그리고 STL 를 학습하게 되었습니다. (불쾌)

지난 주말 중 많은 시간을 할애했으나 원하는 방식으로는 못 풀고

STL 로 허무하게 통과되어 찝찝한 상태입니다.

실패한 코드에서 개선할 점을 지적해주시면 감사드리겠습니다.

3. 코드

1) 성공 (10,000KB 116ms)

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
24479_알고리즘 수업 - 깊이 우선 탐색 1
10000KB	116ms
*/
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int LM = 100001;
vector<int> graph[LM];
int visited[LM], seq = 1;

void dfs(int r) {
	visited[r] = seq++;

	for (int i = 0; i < graph[r].size(); i++) {
		if (!visited[graph[r][i]]) dfs(graph[r][i]);
	}
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int n, m, s, u, v;
	scanf("%d %d %d", &n, &m, &s);

	for (int i = 1; i <= m; i++) {
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
		if (u != s) graph[v].push_back(u);
	}

	for (int i = 1; i <= n; i++) sort(graph[i].begin(), graph[i].end());
	dfs(s);

	for (int i = 1; i <= n; i++) printf("%d\n", visited[i]);
	return 0;
}

 

2) 실패 (91% 시간 초과)

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
24479_알고리즘 수업 - 깊이 우선 탐색 1
91% 시간초과
*/
#include <cstdio>

const int LM = 100001;
int visited[LM], seq = 1;

struct _node {
	int id;
	_node* next;
} node[LM * 5]; // dummy + M * 2(undirected)
int nIdx;

_node* getNode(int id) {
	node[nIdx].id = id;
	return &node[nIdx++];
}

_node* adj[LM];

void addNode(_node* head, _node* newNode) {
	newNode->next = head->next;
	head->next = newNode;
}

void sSort(_node *head) {
	_node* curi = head;
	_node* curj;
	_node* minNode;
	int min;

	while (curi) {
		minNode = curi;
		min = curi->id;

		curj = curi->next;
		while (curj) {
			if (curj->id < min) {
				minNode = curj;
				min = curj->id;
			}
			curj = curj->next;
		}

		if (min != curi->id) {
			minNode->id = curi->id;
			curi->id = min;
		}
		curi = curi->next;
	}
}

void dfs(_node* node) {
	visited[node->id] = seq++;
	_node* next = node->next;
	while (next) {
		if (!visited[next->id]) dfs(adj[next->id]);
		next = next->next;
	}
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int n, m, s, u, v;
	scanf("%d %d %d", &n, &m, &s);

	for (int i = 1; i <= n; ++i) adj[i] = getNode(i);

	while (m--) {
		scanf("%d %d", &u, &v);
		addNode(adj[u], getNode(v));
		if (u != s) addNode(adj[v], getNode(u));
	}

	for (int i = 1; i <= n; ++i) {
		_node* head = adj[i]->next;
		if (head) sSort(head);
	}

	dfs(adj[s]);

	for (int i = 1; i <= n; ++i) printf("%d\n", visited[i]);
	return 0;
}