[BOJ/백준] 2668 숫자고르기 (G5)

문제

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

풀이

문제를 보면 표는 두 줄로 구성되어 있으며, 첫째 줄에는 1부터 N까지의 숫자가 순서대로, 둘째 줄에는 임의의 1이상 N 이하의 숫자가 들어 있다. 첫째 줄에서 숫자를 선택해서, 선택한 숫자들과 그 아래 둘째 줄의 숫자들이 이루는 집합이 일치해야 한다. 그리고 선택된 숫자들의 개수가 최대가 되어야 한다.

 

각 숫자에서 시작하여 둘째 줄의 숫자를 따라가다가 출발 숫자를 다시 만나면 사이클이 형성된다. 사이클을 찾기 위해 DFS를 사용했다. 각 숫자의 출발점으로 DFS를 수행하여 사이클을 찾아내고, 그 사이클에 속하는 숫자들을 결과 리스트에 추가한다.

DFS 탐색 중에 각 숫자가 여러 번 방문되지 않도록 방문 처리를 하고, 각 탐색이 끝난 후에는 방문 처리를 초기화하여 다른 숫자에 대한 탐색에 영향을 주지 않도록 하였다.

 

DFS로 사이클을 찾아서 푸는 문제는 처음이여서 DFS로 어떻게 접근해야 하는지 방법을 찾는 데 시간이 오래 걸렸다. 

Code

import java.io.*;
import java.util.Collections;
import java.util.LinkedList;

public class Main {

    static int N, num;
    static int[] graph;
    static boolean[] visited;
    static LinkedList<Integer> result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        graph = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            graph[i] = Integer.parseInt(br.readLine());  // i번째 인덱스에 값
        }

        visited = new boolean[N + 1];
        result = new LinkedList<>();

        for (int i = 1; i <= N; i++) {
            visited[i] = true;
            num = i;
            dfs(i);
            visited[i] = false;  // 다른 숫자를 시작점으로하여 다시 dfs를 해야하기 때문에 false 처리
        }
        Collections.sort(result);
        bw.write(result.size() + "\n");
        for (int i = 0; i < result.size(); i++) {
            bw.write(result.get(i) + "\n");
        }
        bw.flush(); bw.close();
    }

    // dfs 로직 : 출발 숫자 -> graph[출발 숫자] -> graph[graph[출발 숫자]]를 반복하다가 출발 숫자를 다시 만나게 되면, 첫째 줄과 둘째 줄의 정수들의 집합이 일치한다고 볼 수 있다.
    static void dfs(int now) {  // 시작 인덱스와 다음 인덱스로 dfs 진행. 다음 노드는 graph[now](graph의 인덱스 i가 현재 노드이고, graph[i]가 다음 노드이므로)
        // 현재 노드의 now 값이 처음 dfs를 시작한 값(num)과 같다면 사이클이 완성된것이므로 result에 추가
        if (graph[now] == num) result.add(num);

        // 다음 노드 검사
        if (!visited[graph[now]]) {  // graph의 현재 노드가 방문하지 않은 곳이라면?
            visited[graph[now]] = true;  // 현재 노드를 방문 처리
            dfs(graph[now]);  // dsf 재귀 호출로 다음 노드를 방문
            visited[graph[now]] = false;  // 재귀 호출 종료 후 방문 처리 해제
        }
    }
}