혼자 놀기의 달인 (DFS)

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

프로그래머스

 

문제 풀이

• cards의 최대가 100이므로, 시간 복잡도를 꽤나 넉넉히 가져가도 됨 (완전 탐색 사용 가능)
• 반복해서 숫자 카드를 뽑고, 상자를 여는 부분을 반복문으로 만들어도 되고 DFS를 통해 구현해도 됨

 

 

작성한 코드 (반복문 사용)

import java.util.*;

public class Solution {

    public int solution(int[] cards) {
        int answer = 0;
        
        // visited 설정
        boolean[] isOpened = new boolean[cards.length];
        Arrays.fill(isOpened,false);

        // 그룹 별 count를 보관하는 List
        List<Integer> group = new ArrayList<>();

        // 카드 뽑기 진행
        for (int i = 0; i < cards.length; i++) {
            doGame(i,cards,isOpened,group);
        }
        
        // 정렬(내림차순)
        Collections.sort(group, Comparator.reverseOrder());

        // 전체가 한 사이클 그룹인 경우의 처리 (없으면 런타임 에러)
        if (group.size() == 1) return 0;
        
        answer = group.get(0) * group.get(1);
        return answer;
    }

    private void doGame (int startIndex, int[] cards, boolean[] isOpened, List<Integer> group) {

        if (isOpened[startIndex]) return;

        int count = 0;
        int nowCard = startIndex+1;

        while (true) {
            int newCard = cards[nowCard-1];

            if (isOpened[nowCard-1]) break;
            isOpened[nowCard-1] = true;

            nowCard = newCard;

            count++;
        }

        group.add(count);
    }
}