목차
문제 정보
https://www.acmicpc.net/problem/2668
2668번: 숫자고르기
세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절...
www.acmicpc.net
난이도 : G5
유형 : 그래프탐색, DFS
문제 풀이
싸이클을 구하는 문제이다.
필자는 재귀가 아닌 while반복문으로 풀었다.
이문제에는 재귀보단 반목문이 더 최적화인 풀이일 것이다. ( 메모리, 시간이 더 적게 소모된걸 확인)
윗줄에서 숫자 1개를 선택했을 때 결국 다시 뽑은 숫자로 돌아오는지 확인해 주면 된다
ex)
1 | 2 | 3 | 4 | 5 | 6 |
2 | 4 | 1 | 3 | 6 | 5 |
1 - > 2 - > 4 - > 3 - > 1 => 싸이클
5 - > 6 - > 5 => 싸이클
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
private int N;
private boolean[] isVisited;
private int[] numbers;
public void solution() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
numbers = new int[N + 1];
for (int i = 1; i <= N; i++) {
numbers[i] = Integer.parseInt(br.readLine());
}
ArrayList<Integer> list = new ArrayList<>();
for (int i = 1; i <= N; i++) {
isVisited = new boolean[N + 1];
if (i == numbers[i]) {
isVisited[i] = true;
list.add(i);
continue;
}
if (!isVisited[i]) {
isVisited[i] = true;
int root = i;
int next = numbers[root];
while (!isVisited[next]) {
isVisited[next] = true;
next = numbers[next];
}
if (next == root) {
list.add(root);
}
}
}
Collections.sort(list);
sb.append(list.size()).append('\n');
for (int e : list) {
sb.append(e).append('\n');
}
System.out.println(sb);
}
public static void main(String[] args) throws IOException {
new Main().solution();
}
}
'Algorithm, Problem Solving > 백준(boj)' 카테고리의 다른 글
[백준][Java] 15486 - 퇴사 2 (0) | 2023.03.28 |
---|---|
[백준][Java] 6593 - 상범 빌딩 (0) | 2023.03.27 |
[백준][Java] 2023 - 신기한 소수 (0) | 2023.03.26 |
[백준][Java] 20055 - 컨베이어 벨트 위의 로봇 (0) | 2023.03.26 |
[백준][Java] 9084 - 동전 (0) | 2023.03.25 |
댓글