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

 

예제 입력

7
3
1
1
5
5
4
6

예제 출력

3
1
3
5

 

index의 목록과 board[index] 목록의 정렬값이 같아야 하는 문제

 

1 2 3 4

2 3 4 1

예를들어 index인 파란색 숫자와 값인 빨간색 숫자의 목록(정렬)은 [1 2 3 4] 와 [1 2 3 4] 같으므로

예제 4 4 3 2 1 은 맞는 값이다

 

위 조건을 만족시키려면 그래프가 이어져야 하고 다시 첫번째 index와 만나야한다

1>2 2>3 3>4 4>1

그래서 for문으로 1~N까지 index를 전송해주고 bfs에 따로 int first 로 저장해둔다

그리고 큐에 first를 넣어주고 while문으로 넘어간다

 

while문에서는

아직 방문하지 않은 index에 해당하는 값을 큐에 저장한다

만약 index에 해당하는 값이 아까 저장한 first값과 같으면 해당 값을 subArr에 저장하고

한바퀴 돌았다는 표시로 isCycle를 true로 변경시킨다

while문을 다 돌고 한바퀴 돌았으면 해당 방문 목록을 return해서 저장하고

해당 리스트도 저장한다 (반복)

 

import java.util.*;

public class B2668 {
    static int N;
    static int[] board;
    static boolean[] visited;
    static ArrayList<Integer> arr = new ArrayList<>();

    public static boolean[] bfs(int first, boolean[] visited){
        Queue<Integer> queue = new LinkedList<>();
        visited[first] = true;
        queue.add(first);
        boolean isCycle = false;
        ArrayList<Integer> subArr = new ArrayList<>();

        while(!queue.isEmpty()){
            int temp = queue.remove();
            if(board[temp]==first){
                subArr.add(board[temp]);
                isCycle = true;
                break;
            }
            if(visited[board[temp]]) continue;
            visited[board[temp]] = true;
            subArr.add(board[temp]);
            queue.add(board[temp]);
        }

        if(isCycle) {
            arr.addAll(subArr);
            return visited;
        }
        return null;
    }

    public static void main(String[] args) {
        Scanner sc =  new Scanner(System.in);
        N = sc.nextInt();
        board = new int[N+1];
        visited = new boolean[N+1];
        for(int i=1; i <N+1; i++){
            board[i] = sc.nextInt();
        }

        for(int i=1; i <N+1; i++){
           boolean[] after = bfs(i, visited.clone());
           if(after!=null){
               visited = after;
           }
        }

        Collections.sort(arr);
        System.out.println(arr.size());
        for(int i : arr){
            System.out.println(i);
        }
    }
}