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

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

2668번: 숫자고르기

 

---

 

1행에 있는 숫자들을 선택했을 때... 아래 2행에 있는 숫자들이 똑같은 집합을 가져야 한다.

 

뭔가 정확히는 모르겠지만 숫자들끼리 연결이 있어야 할 것 같아서

이리저리 끄적이다가

출발노드에서 dfs과정을 거쳐서 다시 내 노드로 돌아온다면 조건에 적합하다는걸 알았다.

그래서 모든 노드에 대해서 이 조건이 적합한지 알아내서, 적합하다면 리스트에 추가했다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

public class P2668 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br=  new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		int[] arr= new int[n+1];
		boolean [] visited = new boolean[n+1];
		for(int i=1;i<n+1;i++) {
			arr[i]=Integer.parseInt(br.readLine());
		}
		LinkedList<Integer> result =new LinkedList<>();
		for(int i=1;i<n+1;i++) {
			if(isCycle(i,arr,visited)) {
				result.add(i);
			}
		}
		System.out.println(result.size());
		for(int i=0;i<result.size();i++) {
			System.out.println(result.get(i));
		}
		
		
	}
	static boolean isCycle(int v,int[] arr,boolean[] visited) {
		for(int i=0;i<visited.length;i++) {
			visited[i]=false;
		}
		visited[v]=true;
		
		int next=arr[v];
		
		while(visited[next]==false) {
			visited[next]=true;
			next=arr[next];
		}
		
		if(next==v)
			return true;
		return false;
	}

}

 dfs 재귀함수로 만들려고 했는데

처음 시작한 노드로 돌아가는지 알기 위해서는 재귀를 쓸 수 없었다.

그래서 isCycle 내부를 반복문으로 작성했다.

(한 노드에서 갈 수 있는 노드가 하나여서 간단했다)