[BOJ] 2668: 숫자 고르기 (JAVA)

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

 

풀이

 

DFS로 문제를 해결했다.

N이 최대 100개였기 때문에 List사용해서 문제를 해결했다.

 

 

예제로 설명해보자면, 

 

윗줄에 있는 숫자를 넣어주는 list

아랫줄에 있는 숫자를 넣어주는 list2

 

시작점인 now가 0이라면, list에는 arr[0][0]인 1을 넣어주고, visited[0][0] = true처리

list2에는 arr[0][1]인 3을 넣어주고, visited[0][1] = true처리 해준다.

그리고, Check()메서드에 arr[0][1]-1을 넣어 다시 재귀를 반복해준다.

 

재귀를 반복하다보면 어느 순간 방문처리 되어있는 곳을 다시 방문하게 되는데,

그럼 이제 재귀를 그만 돌고 list와 list2에 들어있는 숫자들이 같은지 확인을 해주면 된다.

 

전체코드

package CodingTest;

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

public class 골드5_2668_숫자고르기 {
	static int N;
	static int arr[][];
	static boolean visited[][];
	static List<Integer> list = new ArrayList<>();
	static List<Integer> list2 = new ArrayList<>();
	static List<Integer> ans = new ArrayList<>();
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
		N = Integer.parseInt(br.readLine());
		
		arr = new int[N][2];
		for(int i=0; i<N; i++) {
			arr[i][0] = i+1;
			arr[i][1] = Integer.parseInt(br.readLine());
		}
		
		for(int i=0; i<N; i++) {
			list.clear();
			list2.clear();
			visited = new boolean[N][2];
			Check(i);
		}
		
		Collections.sort(ans);
		sb.append(ans.size()).append('\n');
		for(int i=0; i<ans.size(); i++) {
			sb.append(ans.get(i)).append('\n');
		}
		
		bw.write(sb.toString());
		bw.close();
	}
	public static void Check(int now) {
		if(visited[now][0]) {
			int cnt = 0;
			Collections.sort(list);
			Collections.sort(list2);
			for(int i=0; i<list.size(); i++) {
				if(list.get(i) == list2.get(i)) {
					cnt++;
				}
			}
			if(cnt == list.size()) {
				for(int i=0; i<list.size(); i++) {
					if(!ans.contains(list.get(i))) {
						ans.add(list.get(i));
					}
				}
			}
			return;
		}else {
			visited[now][0] = true;
			visited[now][1] = true;
			list.add(arr[now][0]);
			list2.add(arr[now][1]);
			Check(arr[now][1]-1);
		}		
	}
}