BOJ) 숫자고르기

숫자고르기

2668번: 숫자고르기

풀이

 

어제 풀었던 사이클 문제와 비슷한 것 같은데, 이 문제는 BFS로 풀었다. (사실 어제 푼 방법이 기억에 남지 않았다.)

1~N번까지 순회하면서 해당 인덱스가 가진 값을 타고 가는 검사를 통해, 시작한 인덱스 i번이 나오면 답에 추가를 해줬다.

 

위의 값을 가지고 있다면, 1번~ 7번까지 순회를 하면서 답을 찾는 것이다.

1번 index는 3이라는 값을 가지고 있다.

이 3이라는 값을 LinkedList에 넣고, 탐색을 한다.

3번 인덱스를 들어가서 값을 확인하고, 탐색을 처음 시작한 인덱스인 1이 나오기 때문에 1은 답이 된다.

 

2번 인덱스는 1번 값을 가지고 있으므로, 위의 과정을 따라가면 2가 나올 수 없기 때문에, 답이 될 수 없다.

 

3번은 1번 인덱스의 탐색과 반대로 1로 이동해서 3이라는 자기 자신을 만나기 때문에 답이 된다.

 

5번은 바로 자기 자신의 인덱스를 만나기때문에 답이 된다.

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] numArr = new int[n+1];
        for(int i=1; i<=n; i++)  numArr[i] = Integer.parseInt(br.readLine());
        br.close();
        solution(n,numArr);
    }

    private static void solution(int n, int[] numArr) {
        ArrayList<Integer> ansList = new ArrayList<>();
        for(int i=1; i<=n; i++) {
            LinkedList<Integer> moveList = new LinkedList<>();
            moveList.offerFirst(numArr[i]);
            boolean[] visit = new boolean[n+1];
            while(!moveList.isEmpty()) {
                int now = moveList.poll();
                if(now == i) {
                    ansList.add(i);
                    break;
                }
                if(!visit[numArr[now]]) {
                    moveList.offer(numArr[now]);
                    visit[numArr[now]] = true;
                }
            }
        }
        StringBuffer sb = new StringBuffer();
        final String NEWLINE = "\n";
        sb.append(ansList.size()).append(NEWLINE);
        for(int num : ansList) sb.append(num).append(NEWLINE);
        System.out.println(sb.toString());
    }
}