[PS] Programmers - 혼자 놀기의 달인 ( DFS )

프로그래머스

 

◎ 문제풀이

 

상자 안에는 다음 오픈할 상자의 번호가 적혀있는 카드가 들어있다. 임의의 한 상자를 오픈하여 연달아 오픈해서 이미 오픈한 상자를 만날 때까지 오픈한다고 했을 때, 연달아 오픈할 수 있는 상자의 개수가 가장 많은 것과 그 다음 많은 것의 곱을 구하는 문제이다. 

 

문제가 복잡해보이지만 싸이클을 찾는 문제이다. 

방향그래프에서 싸이클을 찾는 문제는 DFS 알고리즘을 사용하면 된다.

 

DFS 알고리즘으로 가장 큰 싸이클과 그 다음 싸이클을 찾아서 싸이클 안의 상자수를 곱하면 된다.

 

주의할 점은 입력으로 주어진 배열은 0부터 인덱스가 시작하므로 1부터 시작하는 배열을 새로 만들어줘야한다. ( 문제를 잘못 이해해서 여기서 조금 헤매었다. )

 

 

◎ 코드

class Solution {
    
    boolean[] visited;
    boolean[] isCycle;
    int cycleCount;
    int[] boxArr;
    
    public int solution(int[] cards) {
        
        boxArr = new int[cards.length+1];
        
        for(int i=0;i<cards.length;i++){
            boxArr[i+1] = cards[i];
        }

        visited = new boolean[cards.length+1];
        isCycle = new boolean[cards.length+1];
        
        int boxGroup1 = 0;
        int boxGroup2 = 0;
        
        for(int i=1;i<boxArr.length;i++){
            
            if(isCycle[i]) continue;
            
            cycleCount = 0;
            dfs(i);
            
            if( cycleCount > boxGroup1 ){
                boxGroup2 = boxGroup1;
                boxGroup1 = cycleCount;
            }
            else if( cycleCount == boxGroup1){
                boxGroup2 = cycleCount;
            }else{
                if( cycleCount > boxGroup2) boxGroup2 = cycleCount;
            }
            
        }
        
        return boxGroup1 * boxGroup2;
            
 
    }
    
    public void dfs(int num){
        int nextNum = boxArr[num];
        
        if(visited[nextNum]) {
            if(isCycle[num]) return;
            
            isCycle[num] = true;
            cycleCount++;
        }else{
            visited[nextNum] = true;
        }
        
        dfs(nextNum);
        
    }
}