[Java] BOJ 2668번 숫자고르기

2668번: 숫자고르기

---

풀이

DFS를 사용하여 해결했습니다.

문제를 잘못이해하여 생각보다 어렵게 해결했던 문제입니다.

문제에서 요구하는 것은 표가 주어졌을때, 표를 배열 arr이라고 생각하고 arr의 모든 인덱스 idx를 DFS의 시작점으로 탐색합니다.

만약 arr[idx] 가 찾고자하는 idx와 같다면 이는 문제에서 요구하는 조건에 맞아 떨어지므로 list에 추가하면 되고 다르다면 arr[idx]로 DFS를 수행하면 됩니다.

자세한 사항은 코드의 주석을 참고해주세요.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
	public static int N, idx;
	public static boolean[] visited;
	public static int[] arr;
	public static List<Integer> answer;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		arr = new int[N + 1];
		visited = new boolean[N + 1];
		answer = new ArrayList<Integer>();
		
		for (int i = 1; i <= N; ++i) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		// 인덱스를 기준으로 DFS를 수행
        // 모든 인덱스에 대해서 DFS를 수행하게 된다.
		for (int i = 1; i <= N; ++i) {
			visited[i] = true;
			// 현재 찾고자하는 인덱스를 저장
			idx = i;
			// 해당 인덱스부터 시작하여 DFS 탐색을 통해 arr에 같은 숫자가 있는지 탐색
			go(i);
			visited[i] = false;
		}
		
		// 작은 수 부터 출력해야 하므로 정렬
		Collections.sort(answer);
		
		StringBuilder sb = new StringBuilder("");
		sb.append(answer.size()).append("\n");
		
		for (int n : answer) {
			sb.append(n).append("\n");
		}
		
		System.out.print(sb);
	}
	
	public static void go(int i) {
		// 조사하고자하는 idx 번호와 현재 DFS로 들어온 인데스의 값 즉 arr[i]와 같다면
		// 조건에 부합하므로 리스트에 추가
		if (arr[i] == idx) {
			answer.add(i);
		}
		
		// 방문하지 않은 숫자라면 arr[i]의 숫자로 DFS 수행
		if (!visited[arr[i]]) {
			visited[arr[i]] = true;
			go(arr[i]);
			visited[arr[i]] = false;
		}
	}
}

---

pyo7410/Algorithm