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

1. 문제

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

2668번: 숫자고르기

 

 

2. 풀이 과정

흔히 union & find를 구현할 때, find에서 사이클 여부를 판단한다.

이 문제는 find의 로직과 유사하게 구현할 수 있다.

사이클이 되는 모든 값을 결과로 출력하면 되는 문젠데, 처음부터 그래프 유형인걸 파악못해서 시간이 걸렸다.

 

1. for문으로 첫 번째 줄의 값을 처음부터 끝까지 탐색한다.

2. 각 값마다 cycle이 되는지 확인하고, cycle이면 결과 값에 담는다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

    static int N, cnt;
    static int[] arr;
    static boolean[] visited;
    static StringBuilder sb;

    public static void main(String[] args) throws Exception {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N + 1];
        visited = new boolean[N + 1];
        sb = new StringBuilder();

        for(int i=1; i<=N; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        for(int i=1; i<=N; i++){
            visited[i] = true;
            dfs(i, i);
            visited[i] = false;
        }
        System.out.print(cnt);
        System.out.print(sb);
    }

    public static void dfs(int start, int now){
        if(arr[now] == start){
            cnt++;
            sb.append("\n").append(start);
            return;
        }

        if(!visited[arr[now]]){
            visited[arr[now]] = true;
            dfs(start, arr[now]);
            visited[arr[now]] = false;
        }
    }

}

 

 

결과