[백준_2668번] 숫자고르기

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

2668번: 숫자고르기

[문제]

 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자.

 이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다. 이때 집합의 크기는 3이다. 만약 첫째 줄에서 1과 3을 뽑으면, 이들 바로 밑에는 정수 3과 1이 있으므로 두 집합이 일치한다. 그러나, 이 경우에 뽑힌 정수의 개수는 최대가 아니므로 답이 될 수 없다.

 

[입력 조건]

첫째 줄에는 N(1≤N≤100)을 나타내는 정수 하나가 주어진다. 그 다음 줄부터는 표의 둘째 줄에 들어가는 정수들이 순서대로 한 줄에 하나씩 입력된다.

 

[코드]

import java.util.*;

public class BaekJoon_2668 {
	static ArrayList<Integer> arr=new ArrayList<Integer>();
	static int n,num[];
	static boolean[] visited;
	static int ciycle=0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		num=new int[n+1];
		visited=new boolean[n+1];
		
		for(int i=1;i<=n;i++) 
			num[i]=sc.nextInt();
		
		// 순서대로 사이클이 발생하는지 확인
		for(int i=1;i<=n;i++) {
			visited[i]=true;
			dfs(i,i);
			visited[i]=false;
		}
		
		Collections.sort(arr);
		System.out.println(arr.size());
		for(int i=0;i<arr.size();i++)
			System.out.println(arr.get(i));
	}
	
	// 해당 문제는 싸이클을 이루는 숫자들을 선택하는 문제와 동일하다.
	static void dfs(int start, int target) {
		if(!visited[num[start]]) {
			visited[num[start]]=true;
			dfs(num[start],target);
			visited[num[start]]=false;
		}
		
		// 숫자가 돌고 돌아 target과 같아진다면 싸이클 발생, 해당 숫자를 리스트에 저장한다.
		if(num[start]==target)
			arr.add(target);
	}

}

 

[고찰]

 처음에는 2차원 배열을 선언해 1행에서 숫자를 선택할 때와 2행에서 숫자를 선택했을 때 동일한 경우를 찾으려고 했지만 실패해 다른 사람의 코드를 찾아봤다. 다른 사람의 포스팅을 보고 싸이클을 찾는 문제와 동일하다는 것을 알았다. visited의 인덱스를 다두를 부분이 살짝 헷갈려 적어가면서 이해해보았다. 문제를 보고 이게 어떤 부분을 의도한 것인지 파악하는 능력이 아직 부족한 것 같다.