[백준] 2688 - 숫자고르기 JAVA 자바 풀이

헬로월드! 김컴공입니다.

 

오늘의 문제는 백준 온라인 저지의 2688번 숫자고르기 문제입니다.

그래프를 이용해 빠르게 풀 수 있는 문제인데요, 문제 파악과 풀이 진행해보겠습니다.

 

1. 문제

DFS 를 이용해 그래프를 순회하면서 사이클이 발생하면 그 사이클릭한 경로의 모든 노드를 출력(갯수도 출력)

 

2.풀이

전역 변수로 큐를 선언하고 그래프를 순회하면서 사이클이 발생하면 사이클릭한 경로만 큐에 남도록 처리한 후 큐 안의 모든 노드를 정답 ArrayList 에 넣고, 마지막 출력 시 정렬하고 size 와 반복문을 통한 노드 전체 출력.

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();
    
    static int N;
    static boolean[] check;
    static int[] arr;
    static ArrayList<Integer> ans;
    static Queue<Integer> q;
    
    static void dfs(int n) {
    	check[n] = true;
    	q.add(n);
    	if(q.contains(arr[n]))
    	{
    		while(q.peek()!=arr[n])
    			q.poll();
    		while(!q.isEmpty())
    			ans.add(q.poll());
    		
    		return;
    	}
    	
    	if(!check[arr[n]])
    		dfs(arr[n]);
    }
    
    public static void main(String args[]) throws Exception {
    	N = Integer.parseInt(br.readLine());
    	check = new boolean[N];
    	arr = new int[N];
    	ans = new ArrayList<>();
    	
    	for(int i=0;i<N;i++)
    		arr[i] = Integer.parseInt(br.readLine())-1;
    	
    	q = new LinkedList<>();
    	
    	for(int i=0;i<N;i++)
    	{
    		if(!check[i])
    		{
    			q.clear();
    			dfs(i);
    		}
    	}
    	
    	bw.write(ans.size() + "\n");
    	Collections.sort(ans);
    	for(int n : ans)
    		bw.write(n+1 + "\n");
        bw.flush();
    }
}