[알고리즘]백준 2668: 숫자 고르기

 

해결방법

뽑힌 정수들의 idx들의 집합 = 뽑힌 정수들의 집합을 동일하게 만들어야 한다.

감이 잘 안 잡혀서 풀이를 먼저 읽었는데 ^^ ..

뽑힌 숫자들의 특징은 싸이클을 이루는 숫자들이라고 한다.

문제에서 주어진 숫자들을 예시로 보면

1. 1 → 3 → 1
2. 3 → 1 → 3
3. 5 → 5

따라서 dfs를 통해서 target(처음 시작 인덱스)를 만나면 정답배열에 넣어주도록 코드를 작성하면 되고, O(N^2)의 시간복잡도로 문제를 해결할 수 있게 된다.

 

코드

import java.util.*;
import java.io.*;

// DFS, O(N^2)
public class Main_2668_G5_숫자고르기_DFS {
    static int N;
    static boolean[] visited;
    static int[] numbers;
    static List<Integer> answer;

    public static void dfs(int idx, int target){
        if(numbers[idx]==target) answer.add(numbers[idx]);

        if(visited[numbers[idx]]) return;

        visited[numbers[idx]] = true;
        dfs(numbers[idx], target);
        visited[numbers[idx]] = false;
    }

    public static void main(String[] args) throws IOException{
        // 1. 입력 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        numbers = new int[N+1];
        visited = new boolean[N+1];
        answer = new ArrayList<>();
        for(int i=1; i<N+1; i++) numbers[i] = Integer.parseInt(br.readLine());

        // 2. DFS
        for(int i=1; i<N+1; i++){
            visited[i] = true;
            dfs(i,i);
            visited[i] = false;
        }

        // 3. 출력
        Collections.sort(answer);
        int size = answer.size();
        System.out.println(answer.size());
        for(int i=0; i<size; i++) System.out.println(answer.get(i));
    }
}

 

링크

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