[백준] 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 pq = new PriorityQueue<>(); Queuequ = 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, Queuequ) { 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); } }

결과 화면

from http://nato-blog.tistory.com/157 by ccl(S) rewrite - 2021-11-28 03:27:48