[Gold V][JAVA]2669번:숫자고르기

2669_숫자고르기 - 바로가기

풀이 과정

첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다.

• 사이클 발생 여부는 DFS를 사용하여 출발 숫자 -> arr[출발 숫자] -> arr[arr[출발 숫자]] 이런 방법으로 한 방향 탐색을 해준다.
• 탐색 중 출발 숫자를 만나게 되면 하나의 사이클이 되고 list에 넣어준다.

입력

6
2
3
1
5
4
6

출력

6
1
2
3
4
5
6

잘못된 출력

3
4
5
6

정답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main { //문제유형: DFS , 메모리 제한: 128MB, 시간 제한: 1초
    static int N; // 숫자의 개수
    static int[] array; // 주어진 숫자 배열
    static boolean[] check; // 방문 여부를 체크하는 배열
    static List<Integer> answer; // 결과를 저장할 리스트

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        array = new int[N + 1];
        check = new boolean[N + 1];

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

        answer = new ArrayList<Integer>();

        // 각 숫자에서부터 DFS 수행
        for (int i = 1; i <= N; i++) {
            check[i] = true;
            dfs(i, i);
            check[i] = false;
        }

        Collections.sort(answer);
        System.out.println(answer.size());
        for (int num : answer) {
            System.out.println(num);
        }
    }

    private static void dfs(int index, int start) {
        // 현재 숫자를 방문하지 않았고, 현재 숫자의 다음 숫자가 시작 숫자와 같을 때
        if (!check[array[index]]) {
            check[array[index]] = true; // 다음 숫자를 방문 표시
            dfs(array[index], start);
            check[array[index]] = false; // 다음 숫자 방문 해제
        }
        if (array[index] == start) {
            answer.add(start);
        }
    }
}