[구현과 DFS] 혼자 놀기의 달인

접근

혼자 놀기의 달인

이 문제는 맞았지만
다른 스터디의 풀이법을 참고해보는 것이 좋을 거 같아 정리해보려고 합니다.

저는 DBS를 사용해서 풀지 않았습니다.
전체적인 접근법은 다음과 같습니다.
1. 아무 상자나 연다.
2. 혼자 놀기를 진행하면서 열 수 있는 상자까지 열고 점수를 누적한다.
3. 그 값을 list에 저장한다.

위 과정을 반복하면 list에 혼자 놀면서 생긴 점수들이 저장되어있고
이 list를 정렬시켜 맨 앞에 2개의 값을 더하면
문제에서 구하라는 2회까지의 최대값이 반환된다.

단 맨 앞 값이 카드를 더한 값과 같다면 0을 반환한다.

하지만 위 풀이와 별개로 DFS로 접근한 팀원이 있어
이 방법으로 다시 풀어보았다.

나의 풀이(구현)

import java.util.*;

class Solution {
    public int solution(int[] cards) {
        int answer = 0;
        //카드 총 100장, 각 카드에는 1부터 100까지 숫자가 하나씩
        // 2이상 100이하 자연수 하나를 정해 그 수보다 작거나 같은 숫자 카드 준비
        // 준비한 카드의 수만큼 작은 상자를 준비하면 게임을 시작
        
        // 준비된 상자에 카드 한장씩 넣고 상자를 무작위로 섞어 일렬로 나열
        // 그 일렬에 1번부터 번호 붙이기
        // 상자에서 꺼낸 번호에 해당하는 상자 열기
        // 열어야 하는 상자가 열려 있을 때까지 이게 1회
        
        // 1회만으로 모두 열었으면 0점
        
        // 1번 상자 그룹에 속한 상자의 수 * 2번 상자 그룹에 속한 값
        
        
        // 횟수 넣기
        ArrayList<Integer> turn = new ArrayList<>();
        
        //상자의 번호가 저장된다.
        ArrayList<Integer> box= new ArrayList<>();
        
        // 처음 상자의 시작은 그냥 1번부터
        int index=0;
        
        // 언제 결국 그만두는가에 대한 횟수
        int cnt=0;
        
        
        // 모든 상자가 들어오기 전까지
        while(box.size()<cards.length){
            
        
            //1. 없다면 넣기
            if(!box.contains(index+1)){
                box.add(index+1);
                index=cards[index]-1;
                cnt++;
                // 마지막 박스의 경우에는 turn값에 넣어버리기
                if(box.size()==cards.length) turn.add(cnt); 
            //2. 이미 있으면
            }else{
                turn.add(cnt);
                cnt=0;
                // box에 담아있지 않은 다음 박스 번호를 찾기
                index=findNext(cards,box);
            } 
        }
        
        // 내림차순 정렬
         turn.sort(Comparator.reverseOrder());
        

        
        // 1회에서 마무리되는 경우에는 return 0
        if(turn.get(0)==cards.length) return 0;
        // 구하고자 하는 것은 2회차까지의 값이므로
        return turn.get(0) * turn.get(1);
        
        
         
     
    }
    // 선택되지 않은 다음 박스
    static int findNext(int[] cards, ArrayList<Integer> box){
        
        int length = cards.length;
        
        for(int i=1;i<=length;i++){
            if(!box.contains(i))
                return i-1;
        }
        
        return 0;
        
    }
}

DFS를 이용한 풀이

import java.util.*;

class Solution {
    
    static ArrayList<Integer> list = new ArrayList<>();
    static boolean[] visited;
    public int solution(int[] cards) {
      
        int length = cards.length;
        visited = new boolean[length];
        
        for(int i=0;i<length;i++){
            if(!visited[i]){
                visited[i]=true;
                dfs(1,i,cards);
            }
        }
        
        Collections.sort(list,Collections.reverseOrder());
        
        if(list.size()<2)
            return 0;
        else 
           return list.get(0)*list.get(1);
        
        
        
     
    }
    static void dfs(int level, int boxNum, int[] cards){
        int nextBoxNum = cards[boxNum]-1;
        if(!visited[nextBoxNum]){
            visited[nextBoxNum]=true;
            dfs(level+1,nextBoxNum,cards);
        }else{
            list.add(level);
        } 
        
    }

   
}