📍 문제 설명
https://www.acmicpc.net/problem/2668
💡 접근
범위가 그렇게 크지 않아서 조합으로 풀 수 있겠다 싶었는데, 시간초과가 났다.
1번 ~ n번까지 각 숫자에 대해서 배열에 해당하는 값(인덱스)을 찾아야한다.
idx번의 값과 배열의 idx 인덱스와의 값이 매칭되면 리스트에 넣어주면 된다.
👩💻 코드
import java.io.*;
import java.util.*;
public class Main {
static int[] arr;
static boolean[] visited;
static int n, m, k, t, num;
static ArrayList<Integer> list = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
arr = new int[n+1];
visited = new boolean[n+1];
for(int i = 1; i <= n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
//1~n까지 탐색
//arr 어느 인덱스에 있는지 확인
for(int i = 1; i <= n; i++) {
visited[i] = true;
num = i;
dfs(i);
visited[i] = false;
}
System.out.println(list.size());
for (Integer number : list) {
System.out.println(number);
}
}
private static void dfs(int idx) {
if(arr[idx] == num) {
//System.out.println(num + "은 arr의 " + idx +"번째 인덱스에 있다.");
list.add(num);
}
if(!visited[arr[idx]]) {
visited[arr[idx]] = true;
dfs(arr[idx]);
visited[arr[idx]] = false;
}
}
}
'Algorithm > baekjoon' 카테고리의 다른 글
움직이는 미로 탈출 (0) | 2022.07.27 |
---|---|
말이 되고픈 원숭이 (0) | 2022.07.27 |
샘터 (0) | 2022.07.26 |
일루미네이션 (0) | 2022.07.26 |
회문 (0) | 2022.07.23 |