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

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

2668번: 숫자고르기

풀이

BFS를 응용하여, 첫째 줄의 숫자를 고르면 그 숫자에 둘째 줄에 있는 숫자를 큐에 집어넣는 과정을 반복해서 최종적으로 각 숫자들이 2번씩 포함되는지를 체크하였다.

 

한 사이클을 찾아내면, 첫째 줄과 둘째 줄이 같은 숫자들을 추가하여 크기를 구하여 최대 크기의 사이클을 계속해서 업데이트하는 로직을 생각했다.

 

하지만 사이클이 여러 개 있을 수 있고, 각 숫자는 오직 1개 이하의 사이클에만 포함되므로, 따로 ArrayList<ArrayList<Integer>>에 각 사이클을 저장할 필요 없이 boolean[] 배열을 사용하여 문제를 풀었다.

    static int n;
    static int[] numbers; // numbers[i] = i번째 숫자의 둘째 줄 숫자
    static boolean[] isCycle; // i가 사이클에 포함되어 있으면 true

 

로직

1. numbers를 입력받는다. 이 때 첫째 줄과 둘째 줄의 숫자가 같다면 isCycle[i] = true로 변경한다.

2. 1부터 n까지 각 숫자를 시작점으로 하는 BFS를 수행한다. 이 때 isCycle[i]가 true라면 BFS를 수행하지 않는다.

3. BFS는 큐와 방문배열, Map을 사용한다.

- Map에는 (숫자, 그 숫자가 포함된 횟수)를 저장한다.

- 큐에 시작점의 숫자를 넣는다.

- 큐에서 숫자를 뽑으면 그 숫자에 둘째 줄에 있는 숫자를 큐에 집어넣는다. 이 때 뽑은 숫자와 그 숫자의 둘째 줄 숫자에 대해 Map을 업데이트한다.

- BFS가 종료되고 Map에 각 숫자가 2번 포함되었는지 확인한다. 2번 포함되지 않은 숫자가 있다면 바로 함수를 종료하고, 통과되면 사이클에 포함된 모든 숫자의 isCycle[i] = true로 변경한다.

 

4. 사이클을 생성한 숫자들을 ArrayList<Integer> answer에 저장한다.

5. answer의 사이즈와 숫자들을 차례대로 출력한다. 이미 1부터 순서대로 저장되어있으므로 answer을 따로 정렬할 필요 없다.

 

코드

import java.io.*;
import java.util.*;

public class Main {

    static int n;
    static int[] numbers;
    static boolean[] isCycle;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(br.readLine());
        numbers = new int[n+1];
        isCycle = new boolean[n+1];

        for (int i = 1; i <= n; i++) {
            numbers[i] = Integer.parseInt(br.readLine());
            if (i == numbers[i]) {
                isCycle[i] = true;
            }
        }

        for (int i = 1; i <= n; i++) {
        	if (isCycle[i]) continue;
        	
            bfs(i);
        }

        // 사이클에 저장되어있는 숫자들을 answer에 저장
        ArrayList<Integer> answer = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
        	if (isCycle[i]) {
        		answer.add(i);
        	}
        }
        
        // 순서대로 저장되어 있으니 그대로 출력
        sb.append(answer.size() + "\n");
        for (int num: answer) {
            sb.append(num + "\n");
        }

        System.out.println(sb);
    }

    static void bfs(int start) {
        Queue<Integer> q = new ArrayDeque<>();
        boolean[] visited = new boolean[n+1];
        Map<Integer, Integer> numCnt = new HashMap<>();

        q.add(start);
        visited[start] = true;

        while (!q.isEmpty()) {
            int cur = q.poll();
            int num = numbers[cur];

            numCnt.put(cur, numCnt.getOrDefault(cur, 0)+1);
            numCnt.put(num, numCnt.getOrDefault(num, 0)+1);

            if (visited[num]) {
                break;
            }

            q.add(num);
            visited[num] = true;
        }

        for (int num: numCnt.keySet()) {
            int cnt = numCnt.get(num);
            if (cnt != 2) return;
        }
        
        for (int num: numCnt.keySet()) {
        	isCycle[num] = true;
        }
    }
}