[알고리즘][KOTLIN] 혼자 놀기의 달인

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

프로그래머스

문제 풀이

1. 상자와 카드를 저장하는 box map 을 선언하고 입력으로 들어오는 cards 의 index + 1 을 map 의 key 로 넣고 cards 의 value 를 map 의 value 에 저장한다.

2. 열은 상자를 확인하는 visit 배열을 선언한다.

3. bfs 를 이용하여 상자를 더 이상 열 수 없을 때 까지 반복한다.

4. 이때 3번에서 나온 결과가 상자의 개수와 같으면 문제의 조건에 따라 0 으로 반환한다.

5. 2 ~ 4 번과정을 cards 의 크기 만큼 반복하여 최대 점수를 구한다.

코드

import java.util.*

class Solution {
    fun solution(cards: IntArray): Int {
        var answer: Int = Int.MIN_VALUE
        // 상자와 카드 정보를 저장하는 Map
        val box = Array(cards.size + 1) {
            IntArray(cards.size + 1) { 
                0
            }
        }
        
        cards.forEachIndexed { index, card ->
            box[index + 1][card] = 1
        }
        
        for (i in 1..cards.size) {
            var result = 1
            var gameCount = 0
            val boxes = box
            // 열은 상자인지를 확인하는 visit 배열
            val visit = BooleanArray(cards.size + 1) { false }
            
            for (j in i..cards.size) {
                if (gameCount == 2) break

                if (!visit[j]) {
                    result *= bfs(j, boxes, visit)
                    gameCount++

                    if (result == 0) break
                }
            }
            
            println("result>>>>>> $result")
            
            answer = Math.max(answer, result)
        }

        return answer
    }
    
    fun bfs(start: Int, boxes: Array<IntArray>, visit: BooleanArray): Int {
        val queue = LinkedList<Int>()
        queue.add(start)
        var count = 0
        
        while (queue.isNotEmpty()) {
            val current = queue.pop()
            
            for (i in 1..(boxes.size - 1)) {
                //println("boxes[$current][$i] = ${boxes[current][i]}")
                
                if (!visit[i] && boxes[current][i] == 1) {
                    queue.add(i)
                    visit[i] = true
                    count++
                    break
                    //println("$current, $i, $queue, $count")
                }
            }
        }
        
        // 모든 상자를 다 열었으므로 더 이상 진행할 수가 없기 때문에 조건에 따라 0으로 설정한다.
        if (count == boxes.size - 1) count = 0
        //println("result >>> $count")
        return count
    }
}