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

 

1. 해답 코드

import java.util.*;

class Solution {
    static boolean[] visit;
    static int depth;

    public int solution(int[] cards) {
        int answer = 1;
        int len = cards.length;
        visit = new boolean[len];
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < len; i++) {
            if (!visit[i]) {
                depth = 0;
                open(i, cards);
                list.add(depth);
            }
        }

        if (list.size() < 2) {
            return 0;
        }

        Collections.sort(list, Collections.reverseOrder());
        answer = list.get(0) * list.get(1);
        return answer;
    }

    private static void open(int index, int[] cards) {
        while (!visit[index]) {
            visit[index] = true;
            depth++;
            index = cards[index] - 1;
        }
    }
}

 

2. 해설

노드들이 이어져있고 하나씩 탐색하다가 탐색 할 수 없는 곳에서 멈춘다 -> DFS 문제

 

solution 메서드는 배열을 순회하면서 방문하지 않은 노드를 발견하면 DFS를 시작합니다.

 

open 메서드는 해당 노드를 시작으로 깊이 우선 탐색을 수행하여 사이클을 찾습니다.

사이클의 크기를 기록하고, 모든 사이클을 찾은 후 가장 큰 두 사이클의 크기를 곱하여 반환합니다.