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

프로그래머스 : 혼자 놀기의 달인 (Kotlin)

문제

문제 확인하기

풀이

cards의 길이는 총 상자의 개수이며, cards의 값에는 1부터 cards의 길이까지의 숫자 카드가 존재한다.

그리고 문제를 다시 확인해보자.

• 그 다음 임의의 상자를 하나 선택하여 선택한 상자 안의 숫자 카드를 확인합니다. 다음으로 확인한 카드에 적힌 번호에 해당하는 상자를 열어 안에 담긴 카드에 적힌 숫자를 확인합니다. 마찬가지로 숫자에 해당하는 번호를 가진 상자를 계속해서 열어가며, 열어야 하는 상자가 이미 열려있을 때까지 반복합니다.

이 부분은 DFS 알고리즘을 통해 구현할 수 있다.
상자의 번호를 cards 배열의 인덱스로, 상자안의 값을 cards 배열의 값으로, 상자가 열렸는지 여부는 방문 여부를 체크하는 새로운 배열 visited를 선언하여 최상위 DFS 알고리즘 호출 한번에 하나의 그룹을 얻을 수 있다.
이때, DFS 호출의 결과로 몇 개의 상자를 방문했는지 반환하도록 한다.

visited 배열을 순차적으로 탐색하면서 아직 방문되지 않은 상자에 대해 DFS 알고리즘을 계속해서 호출하도록 한다.

모든 상자에 대해 방문을 마쳤다면, 최상위 DFS 호출이 반환한 방문한 상자의 갯수 중 가장 큰 2개를 곱셈하면 문제가 요구하는 답을 얻을 수 있다.
DFS 호출 한번에 모든 상자를 열었다면 0을 반환하면 된다.

이때 주의할 점은 상자 번호를 가리키는 cards 배열의 인덱스와 카드 숫자를 가리키는 cards 배열의 값이 다르다는 점이다.
배열의 인덱스는 0부터 시작하고, cards 배열의 값은 카드 숫자를 가리키므로 1부터 시작한다.
따라서 카드 번호가 k이면, 다음 선택할 상자 번호는 k-1이 된다.

아래는 코틀린으로 작성한 코드이다.

class Solution {
    lateinit var visited: BooleanArray

    fun solution(cards: IntArray): Int {
        visited = BooleanArray(cards.size)

        var group1 = 0
        var group2 = 0

        for (i in cards.indices) {
            // 현재 상자를 열지 않았으면
            if (!visited[i]) {
                // 현재 상자를 연다.
                visited[i] = true
                // DFS 수행, 이 그룹의 개수를 얻는다.
                val count = dfs(i, cards)
                // 현재 그룹의 개수 저장
                if (count > group1) {
                    group2 = group1
                    group1 = count
                } else if (count > group2) group2 = count
            }
        }

        // 가장 개수가 많은 그룹끼리 곱셉
        // 그룹이 하나뿐이면 group2는 0이 되므로 문제의 요구사항 만족
        return group1 * group2
    }

    fun dfs(idx: Int, cards: IntArray): Int {
        var count = 1
        // cards[idx]는 현재 박스의 카드 숫자
        // 인덱스는 0부터 시작, 카드 번호는 1부터 시작
        // 따라서, 다음 박스의 인덱스는 현재 박스의 카드 숫자 - 1 
        val nextBoxIdx = cards[idx] - 1
        // 다음 박스륿 오픈하지 않았으면
        if (!visited[nextBoxIdx]) {
            // 다음 상자를 연다
            visited[nextBoxIdx] = true
            count = dfs(nextBoxIdx, cards) + 1
        }
        // 현재 박스의 카드 숫자를 박스의 번호로 한다면(가장 깊은 DFS) 1을 반환
        // 그렇지 않으면 DFS가 중첩된 횟수만큼(최상위 DFS 한 번에 방문한 박스 개수만큼) 반환
        return count
    }
}