[백준 JAVA] 2668 숫자고르기

2668 숫자고르기

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

문제설명

각 노드가 다른 노드를 가리키는 그래프에서 사이클을 찾는다.

접근방식

O(N ^ 2) 시간복잡도

 

DFS를 모든 노드에서 호출하고, 각 DFS 호출 시 최대 N개의 노드를 탐색해야 하는 경우를 고려하면

전체 시간복잡도는 O(N ^ 2)이 된다.

• N번의 DFS 호출이 각각 O(N)의 작업을 수행한다.

문제 조건 분석 과정

 

각 노드가 가리키는 노드를 1-based index에서 0-based index로 변환하여 저장한다.

 

• 모든 노드에 대해 DFS를 실행하여 사이클을 찾는다.
• DFS 호출 시, 방문 상태를 체크하고 재귀적으로 다음 노드로 이동한다.
• 현재 노드가 사이클의 시작 노드와 동일하면, 사이클에 해당 노드를 추가한다.
• 사이클을 구성하는 노드를 오름차순으로 정렬하고 출력한다.

 

전체코드

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

public class Main {
    static int num; // 현재 시작 노드를 저장할 변수
    static int[] arr; // 각 노드가 가리키는 노드를 저장하는 배열
    static boolean[] check; // DFS 방문 여부를 기록하는 배열
    static List<Integer> answer; // 사이클의 노드를 저장할 리스트

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

        // 입력된 노드의 개수
        int N = Integer.parseInt(br.readLine());

        // 각 노드가 가리키는 노드를 저장할 배열 초기화
        arr = new int[N];
        check = new boolean[N];

        // 노드의 가리키는 정보를 읽어 배열에 저장
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine()) - 1; // 1-based index를 0-based index로 변환
        }

        // 사이클을 저장할 리스트 초기화
        answer = new LinkedList<>();

        // 각 노드에 대해 DFS를 실행하여 사이클을 찾음
        for (int i = 0; i < N; i++) {
            check[i] = true; // 현재 노드를 방문중으로 표시
            num = i; // 시작 노드를 저장
            dfs(i); // DFS 호출
            check[i] = false; // DFS 종료 후 현재 노드 방문 상태 초기화
        }

        // 결과 리스트를 오름차순으로 정렬
        Collections.sort(answer);

        // 사이클의 노드 개수와 각 노드를 출력
        System.out.println(answer.size());
        for (Integer integer : answer) {
            System.out.println(integer + 1); // 0-based index를 1-based index로 변환하여 출력
        }
    }

    public static void dfs(int i) {
        // 현재 노드가 사이클의 시작 노드와 같다면, 사이클에 추가
        if (arr[i] == num) {
            answer.add(num);
        }

        // 현재 노드가 방문되지 않았다면 DFS를 계속 수행
        if (!check[arr[i]]) {
            check[arr[i]] = true; // 방문 중으로 표시
            dfs(arr[i]); // 다음 노드로 DFS 호출
            check[arr[i]] = false; // DFS 종료 후 방문 상태 초기화
        }
    }
}