프로그래머스 | LV.2 혼자 놀기의 달인 - DFS 문풀 (Java)

⬛ 프로그래머스 | LV.2 혼자 놀기의 달인 - DFS 문풀 (Java)

https://school.programmers.co.kr/learn/courses/30/lessons/131130

프로그래머스

문제 설명

---

💚문제 접근 방식

솔직히 문제만 읽었을 때는 도대체 뭔 말하는 건지 도통 이해가 안됐다 .. 

 

  1) 차례대로 (방문 X) 상자 선택해서 상자에 담긴 카드 번호가 다음 상자 번호가 되는 방식으로 DFS를 계속 깊이 탐색

 

  2) 결과적으로 계속 타고 타고 현재 카드에 대한 다음 상자를 선택했을 때 이미 방문한 상자라면 탐색을 종료 return 하고 그 때의 카운팅 개수를 Q에 담는다.

결국 visited로 방문처리하면서 현재 카드 번호에 따른 다음 상자를 방문하다보면 (이미 방문했단 상자로 되돌아오는) 사이클이 생긴다.

 그때 DFS의 깊이를 종료하고 그때의 count된 소속 상자 개수를 pQ에 담는 방식이다. 

 

  3) 마지막에는 가장 큰 그룹 2개의 count 곱이 정답이 된다.

---

• cards[num]의 값은 현재 상자에서 나온 카드의 번호
• cards[num]-1 은 현재 카드 번호에 따른 다음에 확인해야 할 상자 번호가 된다.

(cards[]가 0번부터 시작하기 때문에 정확한 지칭을 위해 카드번호 -1을 해주는 것이다.)

DFS 풀이 부연 설명

초기 상태: [8, 6, 3, 7, 2, 5, 1, 4]         첫 번째 상자로 0번 상자 연다. 카드 번호 8번 다음 상자 = 8-1 = 7번 상자 두 번째 상자로 7번 상자 연다. 카드 번호 4번 다음 상자 = 4-1 = 3번 상자 세 번째 상자로 3번 상자를 연다 . 카드 번호 7번 다음 상자 = 7-1 = 6번 상자 네 번째 상자로 6번 상자를 연다. 카드 번호 1번 다음 상자 = 1-0 = 0번 상자 (이미 방문했던 상자라 return) → 여기까지 1번의 DFS 호출로 cnt=4개인 그룹이 생긴 것이고, 다음 방문 안한 idx = 1 상자에 대해 DFS 시도하며 그룹핑한다.

---

💚 제출 코드

import java.util.*;
class Solution {
    static PriorityQueue<Integer> queue;
    //DFS
    static void dfs(int[] cards, int num, boolean[] visited, int cnt) {
        // 열었던 상자라면
        if(visited[num]) {
            // 상자의 개수를 queue에 저장하고 리턴
            queue.add(cnt);
            return;
        }
        System.out.println(cards[num]-1);
        visited[num] = true;
        dfs(cards, cards[num] - 1, visited, cnt + 1);
    }
    //솔루션 함수 
    public int solution(int[] cards) {
        int answer = 0;
        
        // cards 크기가 선택한 숫자 n
        int n = cards.length;
        boolean[] visited = new boolean[n];
        
        // 상자 그룹의 개수를 역순으로 저장 pQ -> 담긴 애들 최대 2개 크기 묶어서 return용
        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;
    }
 
}

💚 회고

문제가 하는 말이 무슨 말인지 제대로 파악을 못해서 계속 헤맸다ㅠ 이해하는 데 시간을 많이 뺏겼다. 그냥 내 이해력이 문제일수도 있음