[백준] 2668 - 숫자 고르기

[문제링크]

2668번: 숫자고르기

 

0. Cycle을 탐색하는 DFS문제

 

1. 여러 칸들을 선택했을때, index와 내용이 같으려면 해당 칸들 사이에 cycle이 발생해야한다

• ex. (1,3), (3,5), (5,1)이 있다면, 1->3->5->1로 cycle이 발생하게 된다
• ex2. (2,1), (1,3), (3,5), (5,1)의 경우, 2->1->3->5->1로 2가 누락되니 cycle이 아니다

 

2. 각 칸별로 DFS를 돌며 자기 자신으로 돌아올 수 있는지, 즉 cycle 발생 여부를 탐색한다

• 발생까지 거친 node들은 전부 Queue에 저장한다

 

3. Cycle이 발생했다면, 해당 node들은 cycle에 속한다는 의미로 방문 처리해 DFS 재탐색을 막는다

• 또한 오름차순으로 정렬되도록 PriorityQueue를 사용해 저장한다

 

4. 모든 node에 대한 DFS 탐색이 종료되었다면, PQ의 size와 그 원소를 차례대로 출력한다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main{
	static int[] num;
	static boolean[] isVisit;
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//dfs, 사이클 생성 탐색
		
		int N = pint(br.readLine());
		num = new int[N+1];
		boolean[] isPartOfCycle = new boolean[N+1];
		
		for (int i = 1; i <= N; i++) {
			num[i]=pint(br.readLine());
		}
		
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		Queue<Integer>qu = new LinkedList<>();
	
		for(int i=1; i<=N; i++) {
			if(isPartOfCycle[i])continue;
			
			isVisit = new boolean[N+1];
			//do search
			if(dfs(i,i, qu)) {
				for(Integer element : qu) {
					pq.offer(element);
					isPartOfCycle[element]=true;
				}
			}
			qu.clear();
		}
		
		System.out.println(pq.size());
		while(!pq.isEmpty())System.out.println(pq.poll());
	}
	
	static boolean dfs(int fst, int cur, Queue<Integer>qu) {
		
		if(cur==fst && isVisit[cur])return true;
		if(isVisit[cur])return false;
		qu.offer(cur);
		isVisit[cur]=true;
		return dfs(fst, num[cur], qu);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면