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

2668번: 숫자고르기

---

[DFS]

주어진 배열에서 사이클을 찾아 답을 출력할 배열에 입력하는 것이 목표이다. 나는 기존에 좀 복잡한 방법으로 사이클을 찾고 답을 출력했더니... 시간초과가 발생하였다. 그래서 어떻게 시간을 단축시킬까 하던 도중, 한 블로그를 보고 뒤통수를 맞은 느낌이었다. 너무나 쉬운 코드로 작성한 것을 보고 성찰의 시간을 갖기로 하였다. 블로그의 링크는 하단에 기재한다.

 

참고한 블로그의 풀이방식은 n회 DFS를 수행하며 DFS를 돌다 다음 정점이 처음 시작한 정점이라면 true를 반환하고 그 때의 인덱스를 정답 배열에 저장하는 방식이었다.

 

1 -> 3 -> 1

의 경우 1을 방문하고 3을 방문했는데 3은 다시 1을 가리키므로 1 - 3은 사이클이다. 이때 DFS는 true를 반환하고 1을 result 배열에 저장한다.

# Code </>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int[] arr = new int[101];
    static int[] result = new int[101];
    static boolean[] visit = new boolean[101];
    static boolean flag;

    static void DFS(int x, int start){

        if(!visit[x]){
        
            visit[x] = true;
            DFS(arr[x], start);
        }
        else
            flag = (x == start);
    }

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

        int n = Integer.parseInt(br.readLine());

        for(int i=1; i<=n; i++)
            arr[i] = Integer.parseInt(br.readLine());

        int idx = 0;
        
        visit = new boolean[101];
        
        for(int i=1; i<=n; i++) {
            flag = false;

            DFS(i, i);
            if(flag)
                result[idx++] = i;
        }

        System.out.println(idx);
        
        for(int i=0; i<idx; i++)
            System.out.println(result[i]);
    }
}

# Reference

쓰리디핏님의 블로그