[백준/JAVA] 2668번: 숫자고르기

📖 문제

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

 

 

 

💡  풀이 방식

• DFS

1. 위쪽 줄의 숫자들을 출발지로, 아랫 줄의 숫자들을 도착지로 한 그래프를 생성한다.

2. 그래프 내에서 생성된 사이클을 찾고, 사이클을 만드는  숫자를 리스트에 넣고 오름차순 정렬해 출력한다.

  - 사이클 발생 여부 확인 : [DFS] 출발 숫자 > arr[출발 숫자] > arr[arr[출발 숫자]]

  - 탐색하다가 출발 숫자를 다시 만나면 사이클 하나가 완성된 거고, 이 값을 리스트에 넣는다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] arr;
    static boolean[] visited;
    static List<Integer> list;  // 발생한 사이클 저장용용 리스트
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        
        arr = new int[N+1];
        for(int i = 1 ; i <= N ; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        visited = new boolean[N+1];
        list = new ArrayList<>();
        
        // 순서대로 사이클이 발생하는지 확인인
        for(int i = 1 ; i <= N ; i++) {
            visited[i] = true;
            dfs(i, i);
            visited[i] = false;
        }
        
        Collections.sort(list);
        System.out.println(list.size());
        for(int i : list) {
            System.out.println(i);
        }
    }
    
    // 사이클이 발생하는지 확인하는 메소드
    private static void dfs(int idx, int target) {  // 파라미터 : 시작 idx, 다음 idx
        // 사이클 발생 시, 리스트에 숫자 넣기
        if(arr[idx] == target) {
            list.add(target);
        }
        
        if(!visited[arr[idx]]) {
            visited[arr[idx]] = true;
            dfs(arr[idx], target);
            visited[arr[idx]] = false;
        }
    }
}
 

 

 

---

💦 어려웠던 점

- 안 될 걸 알면서 1~N개 다 뽑는 DFS를 진행할 생각을 했었다,,

 

 

🧐 새로 알게 된 내용

- 해결 아이디어..

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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

 

[백준] 2668: 숫자고르기 - JAVA