[백준 2668] 숫자고르기 (JAVA)

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

2668번: 숫자고르기

DFS를 사용하여 해결할 수 있었다.

1->3->1 , 5->5 와 같이 2번째 값과 1번째 값이 이어지는 것들을 찾으면 된다.

 

1. 배열에 2번째 줄 입력 값을 넣는다.

2. 이어지는 것들을 넣을 arryList, 방문 확인할 배열을 선언한다.

3.  첫번째부터 포문을 돌려서 방문을 표시하고,

해당 인덱스(첫번째 줄 값)을 2번째 줄 값으로 갖고 있는 애들을 확인한다.

 

 

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

public class Main {

	static int[] arr;
	static int n, num;
	static boolean visited[];
	static ArrayList<Integer> reslist;

	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];
		for (int j = 1; j < n + 1; j++) {
			arr[j] = Integer.parseInt(br.readLine());
		}

		reslist = new ArrayList<>();
		visited = new boolean[n + 1];

		for (int i = 1; i < n + 1; i++) {
			visited[i] = true;
			num = i;
			dfs(i);
			visited[i] = false;
		}

		System.out.println(reslist.size());
		Collections.sort(reslist);
		for (int i : reslist) {
			System.out.println(i);
		}
	}

	static void dfs(int idx) {
		if (arr[idx] == num) {
			reslist.add(idx);
		}
		if (!visited[arr[idx]]) {
			visited[arr[idx]] = true;
			dfs(arr[idx]);
			visited[arr[idx]] = false;
		}
	}
}