[BOJ] 백준 2668번 숫자고르기 (Java)

#2668 숫자고르기

난이도 : 골드 5

유형 : 그래프 탐색 / DFS

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)을 나타내는 정수 하나가 주어진다. 그 다음 줄부터는 표의 둘째 줄에 들어가는 정수들이 순서대로 한 줄에 하나씩 입력된다.

▸ 출력

첫째 줄에 뽑힌 정수들의 개수를 출력하고, 그 다음 줄부터는 뽑힌 정수들을 작은 수부터 큰 수의 순서로 한 줄에 하나씩 출력한다.

 

문제 풀이  

사이클을 찾는 그래프 탐색 문제이다. 간단하게 DFS로 구현이 가능하다. 출발점을 지정하고 도착점이 다시 출발점으로 돌아오는 지점을 찾아 체크해주면 된다.

 

설계

1. 주어진 데이터를 인접리스트 배열에 저장한다. list[i].add(num);
2. DFS 탐색을 통해 해당 정수 i의 싸이클 여부를 조사한다. dfs(idx, stack , parent);
   1. s.size()>0 && idx == pa 싸이클이라면 해당 정수를 저장한다.
   2. answer.add(pa);
3. 모든 정수를 탐색한 후 answer를 오름차순으로 정렬하고 답을 출력한다.

 

풀이 코드 

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

public class  Main {
	static List<Integer> answer;
	static List<Integer>[] list;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		answer = new ArrayList<>();
		list = new ArrayList[n+1];
		for(int i=1; i<=n; i++) {
			list[i] = new ArrayList<>();
			int num = Integer.parseInt(br.readLine());
			list[i].add(num);
		}
		
		Stack<Integer> s;
		for(int i=1; i<=n; i++) {
			s = new Stack<>();
			dfs(i,s,i);
		}
		
		System.out.println(answer.size());
		Collections.sort(answer);
		for(int num : answer) {
			System.out.println(num);
		}
	}
	
	static void dfs(int idx, Stack<Integer> s, int pa) {
		if(s.size()>0 && idx == pa) {
			if(!answer.contains(pa)) answer.add(pa);
			return;
		}
		for(int nxt : list[idx]) {
			if(!s.contains(nxt)) {
				s.push(nxt);
				dfs(nxt, s, pa);
				s.pop();
			}
		}
	}
}