[백준-9466]-[DFS]-텀 프로젝트(JAVA)

문제링크 : https://www.acmicpc.net/problem/9466

---

이 문제는  백준_2668번 문제  와 비슷한 문제지만 절대 비슷하게 풀면 큰일 난다.

본인의 2668 번 문제대로 풀었더니 시간 초과가 발생했다.

이전글 보기 --> 2018/11/23 - [알고리즘/BFS_DFS] - [백준-2668]-[DFS]-숫자고르기

어떤 부분이 문제가 될까 확인을 해보니 사이클 조회를 한번 한 이후 초기화 하는 과정에서 시간을 오래 잡아 먹는것으로 파악 됐다. 

먼저 시간 초과가 발생한 소스를 보면서 왜 문제가 있었는지 확인해보고 이 글을 읽는 다른 사람들은 시간초과의 늪에 빠지지 않았으면 좋겠다.

시간초과 소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
/*
 2
7
3 1 3 7 3 4 6
8
1 2 3 4 5 6 7 8
 */
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int testCase = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        
        for(int t = 0; t < testCase; t++) {
            
            
            int studentCnt = Integer.parseInt(br.readLine());
            
            int[] student = new int[studentCnt+1];
            boolean[] visited = new boolean[studentCnt+1];
            
            st = new StringTokenizer(br.readLine());
            // t 번째테스트 케이스의 학생의 값 입력받기
            for(int i=1; i <= studentCnt; i++) {
                student[i] = Integer.parseInt(st.nextToken());
            }
            
            // 학생수만큼 반복하면서 탐색하지 않은 학생을 기준으로 사이클을 돌고
            // 사이클을 만족하면 방문이력은 수정하지 않고 
            // 사이클을 만족하지 못하면 탐색을 진행한 학생들의 방문이력은 초기화 한다.
            int prevCnt = studentCnt;
            for(int i=1; i <= studentCnt; i++) {
                if(!visited[i]) {
                    Queue<Integer> queue = new LinkedList<Integer> ();
                    int remainCnt = cycleDFS(i, i, visited, student, queue, prevCnt);
                    
                    // DFS 탐색전 학생수와 DFS 탐색 후 학생수가 같다면 사이클이 성립되지 않은것.
                    if(prevCnt == remainCnt) {
                        // 큐에 있는 모든 학생의 방문 이력을 초기화 시킨다.
                        while(!queue.isEmpty()) {
                            visited[queue.poll()] = false;
                        }
                    }
                    prevCnt = remainCnt;
                }
            }
            sb.append(prevCnt + "\n");
        }
        System.out.println(sb.toString());
    }
    
    public static int cycleDFS(int startIdx, int idx, boolean[]visited, int[] student, Queue<Integer> queue, int cnt) {
        visited[idx] = true;    // 탐색이력을 참으로 변경한다.
        queue.offer(idx);        // 이번탐색에 탐색된 학생을 큐에저장한다. 실패할경우 큐에 있는 학생들만 방문 이력을 초기화 해주면 된다. 
        
        int nextIdx = student[idx];
        // 시작 인덱스와 다음 인덱스가 같다면 사이클이 성립되는것
        if(startIdx == nextIdx) {
            // 사이클이 성립되면 이번 탐색에 포함된 학생수를 전체 학생수에서 차감하고 그 값을 반환한다.
            return cnt - queue.size();
        }
        
        // 사이클이 성립되지 않았으면 nextIdx를 기준으로 아직 방문하지 않은 인덱스를 탐색한다.
        if(!visited[nextIdx]) {
            return cycleDFS(startIdx, nextIdx, visited, student, queue, cnt);
        }
        
        return cnt; // 사이클이 성립되지 않으면 현재 학생수를 그대로 반환한다. 
    }
 
}
 

백준 2668 문제와 비슷하겠다 생각해서 똑같이 풀었던게 시간초과의 이유였다.

깊게 생각하고 또 다른 힌트들을 수집한 상태에서 문제를 풀었어야 했다. 

49 ~ 54째 줄에서 사이클이 발생하지 않은 인덱스 정보를 다시 초기화 하는과정이 있는데 이 부분에서 시간을 많이 잡아 먹은 것이다. 

그럼 어떻게 접근해야 하는가.. 많은 고민과 많은 검색을 하면서 이해되지 않는 부분들을 찾아갔다. 

첫번째 힌트.

1) 한번 방문한 인덱스는 절대 초기화조차도 해서는 안된다.

문제를 맞춘 모든 사람들이 남긴말.. 근데 사이클이 성립되지 않은것들을 초기화 하지 않으면 어떻게 하지?? 

딜레마에 빠져서 시간을 낭비했다. 

두번째 힌트.

1)  visited 배열을 boolean 타입이 아닌 int 타입의 배열로 변경한다.

2) cycle 의 시작 인덱스를 저장하는 int 타입의 배열을 생성한다. 

boolean 타입의 visited 배열 하나로는 문제를 풀수가 없다고 한다.

세번째 힌트.

1) 사이클의 초점을 꼭 탐색할 인덱스가 시작점으로 돌아와야 한다고 생각하면 안된다.

이 힌트는 내가 고민한건데 생각을 해보니 내가 해결하지 못했던게 너무 모든 사이클의 성립 여부는 시작점에서 돌고돌아 다시 시작점으로 와야 사이클이다.

이렇게 생각을 했던 문제이다. 

즉 2668 문제를 풀었던 순서는 이랬다.

1) 현재 인덱스의 다음 인덱스가 시작점이면 사이클이  성립됐고 탐색을 종료한다.

2) 현재 인덱스의 다음 인덱스가 시작점이 아니고, 방문 이력이 없으면 다음 탐색을 진행한다.

3) 현재 인덱스의 다음 인덱스가 시작점이 아니고, 방문 이력이 없으면 사이클은 성립 되지 않고 탐색이 종료 된다.

위의 순서대로 접근을 하면 방문 이력들을 전부 초기화 해야했다. 

1	2	3
3	1	3

만약 위의 3개의 사이즈를 가진 배열이 들어왔다고 쳤을때 2668 문제를 풀었던 방식대로 탐색이 되면 이렇게 된다.

순서 1: 1번 인덱스를 탐색한다. (visited -> {true, false, false} )

순서 2: 1번 인덱스의 다음 인덱스 3번 인덱스를 탐색한다. (visited -> {true, false, true} )

순서 3: 3번 인덱스의 다음 인덱스 3번은 이미 방문 했으므로 인덱스 1의 사이클이 성립 되지 않는다.

순서 4: 사이클이 성립 되지 않았으므로 1, 3의 visited 정보를 초기화 한다. ( visited -> { false, false, false } )

순서 5: 2번 인덱스의 탐색을 진행한다 -> 순서 1, 2, 3, 4의 반복

순서 6 : 3번 인덱스를 탐색한다. 

순서 7 : 3번 인덱스의 다음 인덱스는 3번이 3번을 탐색한다.

순서 8 : 시작 인덱스는 3번이고 탐색할 인덱스도 3번이니 사이클이 성립된다.

인덱스가 3개 뿐인데 순서를 적기 귀찮을 정도로 같은 많은 반복이 이루어 졌다.

하지만 사이클의 초점을 탐색할 인덱스가 시작 인덱스와 같은지 확인하는게 아니라 탐색할 인덱스와 다음 인덱스가 같은지를 확인하면 위의 번거로운 과정이 많이 줄어든다. 

비교 조건은 3개다. 

1) 다음 인덱스가 이미 탐색을 한 인덱스 이면서 시작 인덱스가 지금 탐색의 인덱스와 같은지

2) 다음 인덱스가 이미 탐색을 한 인덱스 이면서 시작 인덱스가 지금 탐색의 인덱스와 다른지

3) 다음 인덱스가 탐색을 아직 하지 않은 인덱스 인지.

1	2	3
3	1	3

위의 조건으로 소스를 작성하면 다음과 같다.

public static int dfs(int start, int num, int level) {
    visited[num] = level;
    cycle[num] = start;
    
    int next = student[num];
    
    if(visited[next] != 0 && start == cycle[next]) {
        return level - visited[next] +1;
    }else if(visited[next] != 0 && start != cycle[next]) {
        return 0;
    }
    
    return dfs(start, next, level+1);
}

위의 소스를 순서대로 값을 넣어보면 3이 사이클이 성립 되는지는 첫번째 1번 인덱스를 탐색하면서 바로 알 수 있다. 

방문 이력이 있는 인덱스는 현재 사이클이 성립 되는 경우, 사이클이 성립되지 않는데 이전 사이클을 탐색하던 과정에서 방문한 적이 있는 인덱스인경우다.

만약 사이클이 성립된다면 현재 탐색에서 재방문 한거니깐 재방문 할때의 레벨과 전에 방문할때의 레벨의 차를 구하면 사이클이 성립되는 인덱스의 수를 구할 수 있다.

어후 어렵다. 설명하는게 정말 힘들다.

디버깅을 돌려보면서 천천히 이해한다면 이해가 될거라 생각한다.

소스 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
/*
 2
7
3 1 3 7 3 4 6
8
1 2 3 4 5 6 7 8
 */
    
    public static int[] student;
    public static int[] visited;
    public static int[] cycle;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        
        int testCase = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        
        for(int t = 0; t < testCase; t++) {
            
            int studentCnt = Integer.parseInt(br.readLine());
            
            student = new int[studentCnt+1];
            visited = new int[studentCnt+1];
            cycle = new int[studentCnt+1];
            
            st = new StringTokenizer(br.readLine());
            // t 번째테스트 케이스의 학생의 값 입력받기
            for(int i=1; i <= studentCnt; i++) {
                student[i] = Integer.parseInt(st.nextToken());
            }
            
            // 학생수만큼 반복하면서 탐색하지 않은 학생을 기준으로 사이클을 돌고
            // 사이클을 만족하면 방문이력은 수정하지 않고 
            // 사이클을 만족하지 못하면 탐색을 진행한 학생들의 방문이력은 초기화 한다.
            int prevCnt = studentCnt;
            
            int cnt = 0;
            for(int i=1; i <= studentCnt; i++) {
                if(visited[i] != 0) 
                    continue;
                
                if(visited[student[i]] == 0) {
                    cnt += dfs(i, i, 1);
                }
            }
            sb.append((studentCnt - cnt) + "\n");
        }// 테스트 케이스
        System.out.println(sb.toString());
    }
    
public static int dfs(int start, int num, int level) {
    visited[num] = level;
    cycle[num] = start;
    
    int next = student[num];
    
    if(visited[next] != 0 && start == cycle[next]) {
        return level - visited[next] +1;
    }else if(visited[next] != 0 && start != cycle[next]) {
        return 0;
    }
    
    return dfs(start, next, level+1);
}
}