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

알고리즘/DFS

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

잉읭응 2020. 3. 11. 22:34

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

2668번: 숫자고르기

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래

www.acmicpc.net

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;
}