Daily LeetCode Challenge - 2101. Detonate the Maximum Bombs

Problem From.

https://leetcode.com/problems/detonate-the-maximum-bombs/

오늘 문제는 좌표 평면위의 폭탄을 하나 선택해서 터뜨린다고 하였을때, 그로 인해서 터질 수 있는 폭탄의 수 중에 가장 큰 수를 구하는 문제였다.

먼저 graph 를 만든다고 가정하고, 폭탄 하나를 선택했을때, 그와 이어져있는 모든 폭탄을 찾아서 map 형식으로 묶어준다. 피타고라스 정리를 이용하여, 폭탄의 반경안에 다른 폭탄이 들어가있는지 계산하였다.

그런 다음 DFS 를 이용해서 각 폭탄을 터뜨릴때 터질 수 있는 폭탄의 최대 수를 구하였다.

class Solution {
    
    private var answer = 0
    private var chain = 0
    
    fun maximumDetonation(bombs: Array<IntArray>): Int {
        
        val bombMap = mutableMapOf<Int, MutableList<Int>>()
        
        for(i in 0 until bombs.size) {
            for(j in 0 until bombs.size) {
                if(i == j) continue
                val distance = Math.pow((bombs[i][0] - bombs[j][0]).toDouble() , 2.0) + Math.pow((bombs[i][1] - bombs[j][1]).toDouble() , 2.0)
                val area = Math.pow(bombs[i][2].toDouble(), 2.0)
                
                if(distance <= area) {
                    if(bombMap.containsKey(i)) {
                        val list = bombMap[i]!!
                        list.add(j)
                        bombMap[i] = list
                    }else {
                        bombMap[i] = mutableListOf(j)
                    }
                    
                }
                
            }
        }
        
        for(i in bombs.indices) {     
            val visit = BooleanArray(bombs.size) { false }   
            chain = 0
            bombDFS(bombMap, visit, i)
        }
        
        return answer
    }
    
    private fun bombDFS(bombMap: MutableMap<Int, MutableList<Int>>, visit: BooleanArray, index: Int) {
        
        if(visit[index]) return
        visit[index] = true
        
        chain += 1
        
        answer = Math.max(answer, chain)
        
        val nextList = bombMap[index] ?: listOf<Int>()
        
        for(num in nextList) {
            bombDFS(bombMap, visit, num)
        }
        
    }
    
}