문제 탐색하기

입력 자료 정리

1. N은 정수의 개수를 의미한다
2. 이어서 들어오는 n개의 입력값들은 각 순서에서 가리키는 인덱스의 값이다

해결방법 추론

1. 주어진 배열을 확인해보면, 각 인덱스별로 하나의 방향만을 가진다
2. 또한 연결된 방향으로 이동했을 때, 최종적으로 시작지점으로 돌아오는 순환형태인 경우만 정답이된다
3. 이런 형태의 문제는 보통 DFS를 이용하면 쉽게 해결할 수 있다
4. N의 최대 입력값이 100이며, 각 깊이마다 한번의 순회만 이루어지므로
   시간제한안에 문제를 해결할 수 있다!

시간복잡도 계산

1. N개의 정점을 방문할 때, 반복의 횟수가 1이므로 O(n)이 시간복잡도가 된다
2. 따라서 시간제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리

1. 입력값 n은 변수로 관리하며 각 인덱스별 연결된 정보를 관리하기 위해
   리스트 배열을 선언한다. 2차원 배열을 선언해도 되므로 본인의 취향에 맞게 선택하면 된다
2. 정답을 보관할 자료구조를 하나 선언해야한다.
   이때, 중복된 값을 제거하고 오름차순으로 정렬하기 위해 TreeSet을 선택했다
3. 또한 함수의 종료를 위해 방문배열도 선언한다
4. 각 크기는 n+1로 해서, 뽑는 숫자와 같게 한다

구현 코드 설계

1. 1부터 n까지 순회하며, 매 방문배열을 초기화해서 다른 경우에 영향을 주지 않도록 한다
2. dfs를 실행한다. 이때 연결된 정수로 이동하며, start지점과 같은지 확인한다
   만약 같다면 이후 구분하기 위해 start지점 방문을 fasle로 바꾸고 종료한다
3. 아닌 경우 현재 지점의 방문여부를 체크하고,
   방문하지 않은 경우 방문체크 후 재귀함수를 실행한다
4. dfs종료 후에는 시작지점의 방문여부를 체크한다. 방문하지 않았다면, 방문체크한다
5. 이어서 1부터 n+1까지 탐색하며, 방문한 지점을 ans에 넣는다

출력값 설계

1. 완성한 ans의 크기를 출력한다
2. 이어서 ans의 값을 순회하며 모두 출력하면 정답이 된다.

테스트케이스

[테스트케이스-1]
1
1
예상결과:
1
1

[테스트케이스-2]
3
3
2
2
예상결과
1
2

[테스트케이스-3]
10
2
3
4
5
6
7
8
9
10
1
예상결과:
10
1
2
3
4
5
6
7
8
9
10

정답 코드

import java.io.*;
import java.sql.Array;
import java.util.*;

/**
 * 풀이 과정:
 *
 *
 * 해결방법:
 *
 * 시간복잡도: O()
 * 공간복잡도: O()
 *
 */

public class Main {

    static List<Integer>[] lists;
    static Set<Integer> ans = new TreeSet<>();
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(br.readLine());
        lists = new ArrayList[n+1];
        for (int i = 0; i < n + 1; i++) {
            lists[i] = new ArrayList<>();
        }
        for (int i = 1; i < n+1; i++) {
            int a = Integer.parseInt(br.readLine());
            lists[i].add(a);
        }


        for (int i = 1; i < n + 1; i++) {
            visited = new boolean[n+1];
            dfs(n, i, i);

            if(!visited[i]){
                visited[i] = true;
                for (int j = 1; j < n + 1; j++) {
                    if(visited[j]){
                        ans.add(j);
                    }
                }
            }
        }



        bw.write(ans.size()+"\n");
        for (Integer an : ans) {
            bw.write(an+"\n");
        }

        br.close();
        bw.close();
    }

    private static void dfs(int n, int start, int now) {

        // 순환여부 확인,
        // 순환상태를 기록할 수 있어야 함
        for (Integer i : lists[now]) {
            if(i == start){
                visited[i] = false;
                return;
            }
            if(!visited[now]){
                visited[now] = true;
                dfs(n, start, i);
            }
        }
    }

}

문제 링크

2668번 - 숫자고르기