[백준] 2668-숫자고르기(C++)

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

2668번: 숫자고르기

dfs문제입니다.

N의 범위가 100밖에 안되기 때문에 모든 인자에 대하여 사이클 여부를 확인하는 식으로 진행해도 시간초과가 발생하지 않습니다.

 

 

 

 

1. 각 인덱스마다 해당 값을 사이클을 가지는지 확인합니다.

        1) 방문여부, start와 current의 위치가 같다면 해당값을 포함합니다.

        2) 방문하지 않았다면 방문을 표시하고, arr[current] 로 이동해서 확인합니다.

2. 사이클을 가진다면 해당값을 result배열에 포함합니다. (이때 인덱스가 작은값부터 포함하기 때문에 정렬할 필요가 없습니다.)

 

 

 

정답코드입니다.

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

int n = 0, result_index = 0;
int arr[101] = { 0 };
int visited[101] = { 0 };
int result[101] = { 0 };

void dfs(int current,int start) {
	if (visited[current]) {
		if (current == start)
			result[result_index++] = start;
	}
	else {
		visited[current] = 1;
		dfs(arr[current], start);
	}

}

int main() {
	cin >> n;

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

	cout << result_index << endl;
	for (int i = 0; i < result_index; i++)
		cout << result[i] << endl;
}