[프로그래머스] 혼자 놀기의 달인

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

숫자 카드를 랜덤으로 배열하고, 랜덤으로 골라서 나온 숫자에 해당하는 번호를 가진 다른 카드를 꺼내는 방식으로 그룹 하나를 만들고, 남은 카드도 똑같이 해서 두 번째 그룹을 만들어서 각 그룹의 개수의 곱이 최대가 되도록 하는 문제이다.
만약 두 번째 그룹을 만들 수 없다면 0을 반환하면 된다.

카드고르기

    public int dfs(int start, int[] cards, boolean[] visited) {
        int count = 0;
        while (visited[start]) {
            int next = cards[start];
            visited[start] = false;
            count++;
            start = next;
        }

        return count;
    }

dfs함수는 dfs비스무리한 방식으로 진행돼서 이름을 그렇게 지었다.
해당 그룹에 몇 개가 있는지 저장할 count변수를 선언하고, 이미 방문한 카드가 나오기 전까지 문제에서 말한 방법을 진행했다.
그리고 카드의 개수를 반환했다.

Solution

import java.util.Arrays;

class Solution {
    public int solution(int[] cards) {
        int answer = 0;
        boolean[] visited = new boolean[cards.length + 1];

        for (int start=0;start<cards.length;start++) {
            for (int i = 0; i < cards.length; i++) {
                visited[i + 1] = true;
            }

            int count = dfs(start, cards, visited);
            if (count == cards.length) {
                break;
            }
            for (int i = 0; i < visited.length; i++) {
                if (visited[i]) {
                    boolean[] second = visited.clone();
                    int secondCount = dfs(i, cards, second);
                    answer = Math.max(answer, secondCount * count);
                }
            }
        }

        return answer;
    }
}

모든 번호에 대해서 시작하는 경우를 테스트하려고 for문으로 돌렸다.
그리고 각 시작점에 대해서 dfs함수를 실행했고 개수를 저장했다.
만약 count가 전체 카드의 개수와 같다면 두번째 그룹은 나올 수 없기에 for문을 정지시키고 다음 번호로 넘어갔다.

그렇지 않다면 남은 카드에 대해서도 모두 시작했을 때의 경우를 확인하기 위해서 for문으로 돌렸고 첫번째 탐색으로 생긴 visited를 보존하기 위해서 clone으로 따로 저장하고 dfs함수에 사용하였다.

마지막으로 이렇게 나온 첫번째 count와 두번째 secondCount의 곱을 answer와 비교해서 최대값을 저장했다.