Algorithm, Problem Solving/백준(boj)

[백준][Java] 2668 - 숫자고르기

태오님 2023. 3. 27.

목차

     

    문제 정보

    https://www.acmicpc.net/problem/2668

     

    2668번: 숫자고르기

    세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절...

    www.acmicpc.net

    난이도 : G5

    유형 : 그래프탐색, DFS


    문제 풀이

    싸이클을 구하는 문제이다.

    필자는 재귀가 아닌 while반복문으로 풀었다.

    이문제에는 재귀보단 반목문이 더 최적화인 풀이일 것이다. ( 메모리, 시간이 더 적게 소모된걸 확인)

    윗줄에서 숫자 1개를 선택했을 때 결국 다시 뽑은 숫자로 돌아오는지 확인해 주면 된다

    ex)

    1 2 3 4 5 6
    2 4 1 3 6 5

    1 - > 2 - > 4 - > 3 - > 1   => 싸이클

    5 - > 6 - > 5                     => 싸이클


    코드

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.ArrayList;
    import java.util.Collections;
    
    public class Main {
    
        private int N;
        private boolean[] isVisited;
        private int[] numbers;
    
        public void solution() throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringBuilder sb = new StringBuilder();
    
            N = Integer.parseInt(br.readLine());
            numbers = new int[N + 1];
    
            for (int i = 1; i <= N; i++) {
                numbers[i] = Integer.parseInt(br.readLine());
            }
    
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 1; i <= N; i++) {
                isVisited = new boolean[N + 1];
    
                if (i == numbers[i]) {
                    isVisited[i] = true;
                    list.add(i);
                    continue;
                }
    
                if (!isVisited[i]) {
                    isVisited[i] = true;
                    int root = i;
                    int next = numbers[root];
    
                    while (!isVisited[next]) {
                        isVisited[next] = true;
                        next = numbers[next];
                    }
    
                    if (next == root) {
                        list.add(root);
                    }
                }
            }
    
            Collections.sort(list);
    
            sb.append(list.size()).append('\n');
            for (int e : list) {
                sb.append(e).append('\n');
            }
    
            System.out.println(sb);
        }
    
        public static void main(String[] args) throws IOException {
            new Main().solution();
        }
    }

    댓글