백준 2668번 : 숫자 고르기

 문제

www.acmicpc.net/problem/2668

2668번: 숫자고르기

2668 숫자 고르기

 

 구현 방법

 저는 dfs를 사용하여 구현해주었습니다!

처음에 코드 작성 전 시뮬레이션을 돌려보며 어떻게 구현해야 할까 고민을 많이 한 문제입니다.

더 좋은 방법이 있을거 같은데 제 생각은 여기까지라,, 그냥 이렇게 풀 수도 있구나 참고만 해주셔도 좋을거 같습니다.

 

일단 먼저 인덱스 방문표시, 값 방문표시 해주기 위한 boolean 배열 2개를 선언해 준 후 반복문을 돌려 인덱스0부터 탐색을 해주었습니다.

예제를 예시로 들어 설명해보자면 

해당 예제에는 생각한 값이 안나왔지만 7 5 5 2 1 6 3 1  을 하게 된다면 해당 인덱스를 전부 탐색하기 때문에 중복값이 발생할 수 밖에 없습니다.

tree는 중복값이 허용되지 않고 자동으로 key값이 정렬되므로 tree를 사용해주었습니다.

 

 구현 코드

package BOJ.Gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.TreeSet;

public class B2668_숫자고르기 {
	static boolean[] indexB, valueB;
	static int[] numbers;
	static int N;
	static String temp;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		N = Integer.parseInt(br.readLine());
		indexB = new boolean[N+1];
		valueB = new boolean[N+1];
		numbers = new int[N+1];
		TreeSet<Integer> tree = new TreeSet<>();
		for(int i=1;i<=N;i++) {
			numbers[i] = Integer.parseInt(br.readLine());
		}
		// 입력완료
		
		boolean flag = true;
		for (int i=1;i<=N;i++) {
			dfs(i);
			
			for (int j=1;j<=N;j++) {
				if (indexB[j]!=valueB[j]) {
					flag = false;
					break;
				}
			}
			
			valueB = new boolean[N+1];
			if(!flag) indexB = new boolean[N+1]; // 실패
			else { // 성공
				for (int j=1;j<=N;j++) {
					if (indexB[j]) tree.add(j);
				}
			}
			flag = true;
		}
		
		sb.append(tree.size()+"\n");
		Iterator<Integer> iter = tree.iterator();
		while(iter.hasNext()) {
			sb.append(iter.next()+"\n"); // iterator로 tree 값 출력
		}
		
		System.out.println(sb);
	}
	
	static void dfs(int index) {
		if (indexB[index]) return; // 해당 인덱스를 이미 방문하였다면 Return
		
		indexB[index] = true; // 인덱스 방문표시
		valueB[numbers[index]] = true; // 해당 값 방문표시
		dfs(numbers[index]); // 해당 값을 인덱스 번호로 넘겨줌
	}
}

 

정답!