[G5] 백준 2668번 숫자고르기 C++ DFS, 브루트포스 알고리즘

리뷰

 

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

백트래킹을 시도 했다가, n이 최대 100만에 걸려 시간 초과가 출력되었다.

문제를 보다 보니 첫째줄은 노드를, 둘째줄은 간선을 통해 다른 노드로 이동하는 것으로 보였다.

모든 정점에서 DFS를 진행하여 싸이클이 발생하면 자신을 ans에 추가하는 식으로 구현하였다.

 

 

전역 변수

• n : 주어지는 노드의 개수
• lst : 주어지는 간선의 정보를 저장할 정수형 배열
• v : 방문 처리를 하기 위한 정수형 배열
• ans : 싸이클이 발생한 노드 정보를 추가할 정수형 벡터

 

함수

1. dfs

void dfs(int s, int e)

 

시작 지점으로부터 간선을 타고 노드를 순회하며 사이클 발생 여부를 체크할 함수

1. 기저 조건은 이미 방문한 노드를 재 방문한 경우이다.
2. 이때 시작 지점과 현재 지점이 같을 경우 사이클이 발생한 경우이므로 시작 지점을 ans에 push하고 리턴한다.
3. 기저 조건에 해당하지 않는다면 이동할 노드에 방문처리 후 s, lst[e]를 매개변수로 재귀를 진행한다.

 

문제풀이

1. n값을 입력 받고, lst배열에 n개의 간선 정보를 입력받아준다.
2. n개의 노드를 순회하며 방문 처리를 해제해준 뒤 dfs함수를 통해 깊이 우선 탐색을 진행해 준다.
3. 이때 초기의 s, e는 모두 자기 자신인 상태로 전달해 준다.
4. 모든 dfs탐색을 마치고, ans의 size를 출력한 뒤에 각각의 요소를 출력해 준다.

 

참고 사항

• 노드를 앞에서 부터 돌리기 때문에 자연적으로 정렬된 상태로 출력된다.
• 이미 방문처리 된 곳을 다시 방문하였을때 시작점과 같아야지만 사이클이 발생한 것이다.
• 방문 배열은 매 노드를 초기 깊이 우선 탐색하기 전에 초기화 해주어야 한다.

 

정답 코드

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

int n;
int lst[101];
int v[101];
vector<int> ans;

void dfs(int s, int e) {
	if (v[e]) {
		if (s == e) ans.push_back(e);
		return;
	}

	v[e] = 1;
	dfs(s, lst[e]);
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> lst[i];
	for (int i = 1; i <= n; i++) {
		memset(v, 0, sizeof(v));
		dfs(i, i);
	}

	cout << ans.size() << "\n";
	for (int i : ans) cout << i << "\n";
}