[백준 알고리즘] 백준 2668번 숫자고르기 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 2668번 숫자고르기 자바(Java)

1) 문제번호 : 2668번

 

2) 문제 출처

www.acmicpc.net/problem/2668

2668번: 숫자고르기

2. 문제

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

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

 

 

3. 제약사항

- 

4. 입력

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

 

5. 출력

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

 

6. 풀이

- 각 숫자들마다 DFS를 돌면서 i의 값 즉, 예시에서 나온 2차원 배열에서 0인덱스 행 값이 입력받은 값과 같으면 result라는 ArrayList에 넣어서 i가 N번까지 반복하고 그 결과를 출력하기

7. 소스 코드

import java.util.*;

public class Main {
	static int N;
	static int Num;
	static int[] arr;
	static boolean[] check;
	static ArrayList<Integer> result;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		
		arr = new int[N+1];
		check = new boolean[N+1];
		result = new ArrayList<Integer>();
		
		//입력
		for(int i=1;i<=N;i++) arr[i] = sc.nextInt();
		
		//DFS 시작
		//싸이클 돌기 1부터 N까지
		for(int i=1;i<=N;i++) {
			check[i] = true;
			Num = i;
			DFS(i);
			check[i] = false;
		}
		
		Collections.sort(result);
		
		System.out.println(result.size());
		for(Integer c : result) System.out.println(c);
	}
	
	public static void DFS(int i) {
		if(arr[i]==Num) result.add(Num);
		
		if(!check[arr[i]]) {
			check[arr[i]] = true;
			DFS(arr[i]);
			check[arr[i]] = false;
		}
	}
}

---