백준 2668번
https://www.acmicpc.net/problem/2668

문제

---

생각하기

---

• DFS 백트래킹을 사용했다.

동작

        for (int i = 1; i <= N; i++) {
            visited[i] = true;
            DFS(i, i);
            visited[i] = false;
        }

1부터 N까지 인덱스 탐색을 한다. 자신을 제외하고 기준으로 하여 2번째 줄과 1번째 줄을 넘나들며 재귀를 진행한다.

    private static void DFS(int idx, int target) {
        if (!visited[arr[idx]]) {
            visited[arr[idx]] = true;
            DFS(arr[idx], target);
            visited[arr[idx]] = false;
        }

        if (arr[idx] == target) retList.add(target);
    } // End of DFS()

target과 숫자가 일치하게 되면 retList에 넣어준다.

계속 일치하는 값들만 넣어주면 최대값을 구할 수 있다.

결과

코드

---

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N;
    private static int[] arr;
    private static boolean[] visited;
    private static List<Integer> retList;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();


        for (int i = 1; i <= N; i++) {
            visited[i] = true;
            DFS(i, i);
            visited[i] = false;
        }

        Collections.sort(retList);
        sb.append(retList.size()).append('\n');
        for (int num : retList) {
            sb.append(num).append('\n');
        }

        return sb.toString();
    } // End of solve()

    private static void DFS(int idx, int target) {
        if (!visited[arr[idx]]) {
            visited[arr[idx]] = true;
            DFS(arr[idx], target);
            visited[arr[idx]] = false;
        }

        if (arr[idx] == target) retList.add(target);
    } // End of DFS()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());

        retList = new ArrayList<>();
        visited = new boolean[N + 1];
        arr = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
    } // End of input()
} // End of Main class