import java.io.*;
import java.util.*;
public class number_select_2668 {
static List<Integer> result = new ArrayList<>();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] numbers = new int[n+1];
numbers[0] = 0;
for (int i = 1; i < n+1; i++){
numbers[i] = Integer.parseInt(br.readLine());
}
for (int j = 1; j < n+1; j++){
boolean[] visited = new boolean[n+1];
Arrays.fill(visited, false);
dfs(numbers, visited, j, j);
}
Collections.sort(result);
System.out.println(result.size());
for(int i = 0; i < result.size(); i++){
System.out.println(result.get(i));
}
}
public static void dfs(int[] graph, boolean[] visited, int start, int current){
visited[current] = true;
int next = graph[current];
if (!visited[next]) {
dfs(graph, visited, start, next);
} else if (start == next) {
result.add(start);
}
}
}
코드의 자료구조 및 로직을 설명해드리겠습니다.
자료구조:
List<Integer> result:
선택된 숫자들을 담기 위한 정수형 리스트입니다. 선택된 숫자들이 순서대로 저장됩니다.로직:
main
메소드에서 입력을 받고, 반복문을 통해 숫자를 배열에 저장합니다.numbers
는 입력받은 수열의 각 원소들을 저장하는 배열입니다. 배열의 크기는 입력받은 수열의 크기보다 1 큽니다. (인덱스 0은 사용하지 않음)for
문을 통해 1부터 n까지 반복하면서 dfs
메소드를 호출합니다.dfs
메소드는 재귀적으로 동작합니다. 현재 숫자를 방문했음을 표시하고, 다음으로 이동할 숫자를 결정합니다.dfs
를 호출하여 계속 탐색합니다.result
리스트에 추가합니다.main
메소드에서는 result
리스트를 오름차순으로 정렬한 후, 결과를 출력합니다.위 코드는 주어진 수열에서 숫자를 선택하는 문제를 해결하는 방법입니다. 선택된 숫자들은 result
리스트에 저장되어 출력됩니다.
const readline = require("readline");
let n;
let numbers = [0];
let result = new Array();
function dfs(graph, visited, start, current) {
visited[current] = true;
const next = graph[current];
if (!visited[next]) {
dfs(graph, visited, start, next);
} else if (start == next) {
result.push(start);
}
}
readline
.createInterface(process.stdin, process.stdout)
.on("line", (line) => {
if (!n) {
n = parseInt(line);
} else {
numbers.push(parseInt(line));
}
})
.on("close", () => {
for (let i = 1; i < n + 1; i++) {
let visited = new Array(n+1).fill(false);
dfs(numbers, visited, i, i);
}
result.sort();
console.log(result.length);
result.forEach((element) => {
console.log(element);
});
process.exit();
});
def dfs(graph, visited, start, current):
visited[current] = True
next = graph[current]
if not visited[next]:
dfs(graph, visited, start, next)
elif start == next:
result.append(start)
n = int(input())
numbers = [0]
for i in range(n):
numbers.append(int(input()))
result = []
for j in range(1, n+1):
visited= [False] * (n+1)
dfs(numbers, visited, j, j)
result.sort()
print(len(result))
for ans in result:
print(ans)