(Java) 프로그래머스 - 혼자 놀기의 달인

문제가 잘 이해되지 않아서 몇 번을 읽었다. 이해하고 보니 결국 연결되어 있는 노드의 개수를 저장하고

최댓값 2개를 꺼내서 곱을 반환하면 되는 문제였기에 DFS를 이용해서 풀이했다.

---

로직

cards 배열의 크기가 처음 선택하는 카드의 숫자이기 때문에 visited 배열의 크기를 n으로 설정한다.

첫 번째 상자부터  n번째 상자까지 순회하며 방문하지 않았다면 DFS 메서드를 호출하고 재귀 탐색한다.

열었던 상자까지 도달하면 상자의 개수를 우선순위 큐에 넣고 리턴한다.

모든 순회가 끝나면 우선순위큐의 첫 번째 두 번째 값을 곱해서 answer를 반환한다.

이때 우선순위큐의 사이즈가 1이면 첫 번째 상자 그룹 하나밖에 없다는 의미임으로 0을 반환한다. 

 

최종 코드

import java.util.*;
class Solution {
    static PriorityQueue<Integer> queue;
    public int solution(int[] cards) {
        int answer = 0;
        
        // cards 크기가 선택한 숫자 n
        int n = cards.length;
        boolean[] visited = new boolean[n];
        
        // 상자 그룹의 개수를 저장한 queue
        queue = new PriorityQueue<>(Collections.reverseOrder());
        
        // 열지 않은 상자라면
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                dfs(cards, i, visited, 0);
            }
        }
        
        // queue 크기가 1이면 1번 상자 그룹밖에 없다는 의미
        if(queue.size() != 1) {
            answer = queue.poll() * queue.poll();    
        }
        
        return answer;
    }
    static void dfs(int[] cards, int num, boolean[] visited, int cnt) {
        // 열었던 상자라면
        if(visited[num]) {
            // 상자의 개수를 queue에 저장하고 리턴
            queue.add(cnt);
            return;
        }
        visited[num] = true;
        dfs(cards, cards[num] - 1, visited, cnt + 1);
    }
}