문제 바로가기

나의 풀이

처음에는 각각의 사이클에 대해서 최대의 길이를 가진 하나의 사이클을 구하는 문제인 줄 알았다..

다시보니 각각의 사이클을 모두 더한 리스트를 구하는 것이 문제의 답이었다.

당연히 DFS를 통해 index -> value -> index -> value 이런 식으로 계속 파고 들어야 한다는 생각을 했다. 다른 사람들은 대부분 백트래킹으로 풀었는데 나는 그냥 list 두개를 두고 두개가 서로 일치하면 addAll() 해버리는 식으로 코드를 짰다.

HashSet을 이용해서 중복되는 값이 안생기도록 하다가 ArrayList로 마지막에 바꿔줬다.

나의 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Main {

	static Set<Integer> answer = new HashSet<>();

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = new int[n + 1];

		for (int i = 1; i <= n; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}

		for (int i = 1; i <= n; i++) {
			List<Integer> indexList = new ArrayList<>();
			List<Integer> valueList = new ArrayList<>();
			dfs(arr, indexList, valueList, i);
		}

		List<Integer> list = new ArrayList(answer);
		Collections.sort(list);
		System.out.println(list.size());
		for (Integer integer : list) {
			System.out.println(integer);
		}
	}

	private static void dfs(int[] arr, List<Integer> indexList, List<Integer> valueList, int index) {
		if (indexList.contains(index) || valueList.contains(arr[index])) {
			return;
		}
		indexList.add(index);
		valueList.add(arr[index]);
		if (indexList.containsAll(valueList) && valueList.containsAll(indexList)) {
			answer.addAll(indexList);
			return;
		}
		dfs(arr, indexList, valueList, arr[index]);
	}
}