백준 2668번 숫자고르기(그림 포함) 자바 풀이 및 정답

백준 2668번 숫자고르기 문제 설명

2개의 행으로 이루어진 숫자들이 주어집니다. 1행은 각각 노드이고 이 노드들이 가지고 있는 숫자는 2행에 적혀있습니다. 즉, 각 노드들이 연결된 형태를 이룹니다. 이 중에서 서로 Cycle을 이루는 노드들을 찾는 문제입니다. DFS를 통해 Cycle의 조건을 만족하는 노드들을 찾아나갈 수 있습니다.

 

 

백준 2668번 숫자고르기 그림 설명

012

Cycle조건 파악(그림1)

Cycle의 조건을 파악하는 것이 가장 먼저입니다. 그림처럼 출발지점으로 다시 돌아오는 경우 Cycle이라고 할 수 있습니다. 2,3,4번은 Cycle을 이루고, 5번은 스스로 Cycle을 이루고 있습니다.

 

방법1 Cycle에 해당하는 Path를 통으로 등록(그림2)

Cycle을 코드에서 어떤식으로 등록할까 고민해봐야합니다. 첫 번째 방법으로 Cycle을 이루는 Path를 찾고 그 Path 자체를 등록하는 방법이 있습니다. Path를 검증해야하기 때문에 Path배열과 HashMap으로 해당 노드를 가리킨 노드가 있는지 체크하면서 Cycle인지 아닌지 체크해볼 수 있습니다. Cycle을 한번에 등록하기 때문에 큰 Cycle이 많다면 좋은 방법입니다.

 

방법2 Cycle이면 현재 node만 등록(그림3)

Cycle이라고 확인되면 현재 node를 등록하는 방법입니다. 이미 Cycle인게 확인되었는데도 현재 노드 하나만 정답에 등록하기 때문에 Cycle을 찾았더라도 같은 Cycle을 여러번 돌아야하지만 코드가 간결해지는 장점이 있습니다.

 

 

백준 2668번 숫자고르기 테스트 케이스

## 그림 설명 예시 테스트 케이스
입력
5
5
3
4
2
5

출력
4
2
3
4
5

 

 

방법1. Cycle Path 자체를 등록 - 백준 2668번 숫자고르기 정답 코드(자바)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Collections;
import java.util.ArrayList;
import java.util.HashMap;

public class Main {
    static boolean[] visitedArray;
    public static void main(String[] args) throws IOException{
        BufferedReader brd = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(brd.readLine());
        ArrayList<Integer> answerList = new ArrayList<>();
        visitedArray = new boolean[n+1];

        int[] nodeArray = new int[n+1];
        for (int i=1; i<=n; i++) {
            nodeArray[i] = Integer.parseInt(brd.readLine());
            if (nodeArray[i] == i) {
                visitedArray[i] = true;
                answerList.add(i);
            }
        }

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

            ArrayList<Integer> cyclePath = new ArrayList<>();
            HashMap<Integer, Boolean> cycleCheckMap = new HashMap<>();
            DFS(nodeArray, i, cyclePath, cycleCheckMap);

            boolean isCycle = true;
            for (int x : cyclePath) {
                if (!cycleCheckMap.getOrDefault(x, false)) {
                    isCycle = false;
                    break;
                }
            }
            if (isCycle) { // 사이클이면 cycle를 이루는 모든 node 등록
                answerList.addAll(cyclePath);
                for (int x : cyclePath) {
                    visitedArray[x] = true;
                }
            } else {
                visitedArray[i] = true;
            }
        }

        Collections.sort(answerList);
        System.out.println(answerList.size());
        for (int x : answerList) {
            System.out.println(x);
        }
    }

    static void DFS(int[] nodeArray, int currentNode, ArrayList<Integer> cyclePath, HashMap<Integer, Boolean> cycleCheckMap) {
        visitedArray[currentNode] = true;
        cyclePath.add(currentNode);

        int next = nodeArray[currentNode];
        cycleCheckMap.put(next, true);

        if (!visitedArray[next]) {
            DFS(nodeArray, next, cyclePath, cycleCheckMap);
        }
        visitedArray[currentNode] = false;
    }
}

 

 

 

방법1 Cycle Path 자체를 등록 - 백준 2668번 숫자고르기 정답 코드(자바)

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

public class Main {
    static boolean[] visitedArray;
    public static void main(String[] args) throws IOException {
        BufferedReader brd = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(brd.readLine());

        visitedArray = new boolean[n+1];
        ArrayList<Integer> answerList = new ArrayList<>();
        int[] nodeArray = new int[n+1];
        for (int i=1; i<=n; i++) {
            nodeArray[i] = Integer.parseInt(brd.readLine());
        }

        // 하나씩만 등록하기 때문에 다음 cycle에 지장이 없도록 visited를 false로 변경
        for (int i=1; i<=n; i++) {
            visitedArray[i] = true;
            DFS(i, i, nodeArray, answerList);
            visitedArray[i] = false;
        }

        Collections.sort(answerList);
        System.out.println(answerList.size());
        for (int x : answerList) {
            System.out.println(x);
        }
    }

    static void DFS(int startNode, int currentNode, int[] nodeArray, ArrayList<Integer> answerList) {
        int nextNode = nodeArray[currentNode];

        if (!visitedArray[nextNode]) {
            visitedArray[nextNode] = true;
            DFS(startNode, nodeArray[currentNode], nodeArray, answerList);
            visitedArray[nextNode] = false;
        }

        if (startNode == nodeArray[currentNode]) { // 나에게 돌아오면 나만 등록
            answerList.add(currentNode);
        }
    }
}