[백준 14502] - 연구소(Kotlin)[골드4]

문제

https://www.acmicpc.net/problem/14502

14502번: 연구소

---

문제 설명

일반적인 그래프 탐색문제랑 비슷한 부분이 많다.

조금 다른 점은 벽의 개수를 3개로 제한되어 있다는 점이다. 반드시 3개를 세워서 탐색을 진행한다는 점 말고는 동일하다.

그렇다면 벽 3개를 어디다 배치할지를 결정하면 쉽게 풀 수 있다.

조금 더 효율적인 방법이 있는지는 모르겠지만, 

나는 빈칸의 개수를 배열에 저장해서 

빈칸의개수빈칸의 개수 * 빈칸의 개수 -1 * 빈칸의 개수 -2 만큼 반복문을 돌려서 벽을 지정해 줬다.

배열의 크기가 그렇게 크지 않기 때문에 상관없다고 판단했다.

탐색을 진행하면서 안전영역이 가장 큰 크기를 반환하면 끝이다.

 

코드

fun main(){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val line = br.readLine().split(" ")
    row = line[0].toInt()
    col = line[1].toInt()
    val graph = Array(row,{Array(col,{0})})
    for(i in 0 until row) {
        val line = br.readLine().split(" ")
        for (j in 0 until col) {
            graph[i][j] = line[j].toInt()
            if (graph[i][j] == 0)
                b.add(Pair(i, j))
            if (graph[i][j] == 2)
                q.add(Pair(i, j))
        }
    }
    var answer = 0
    for(i in 0 until b.size){
        for(j in i+1 until  b.size){
            for(k in j+1 until b.size){
                val list : MutableList<Pair<Int,Int>> = LinkedList()
                list.add(b[i])
                list.add(b[j])
                list.add(b[k])
                answer = max(answer,bfs(graph,list))
            }
        }
    }
    println(answer)
}
fun bfs(array : Array<Array<Int>>,list : MutableList<Pair<Int,Int>>) : Int{  //최대한 바이러스가 덜  퍼지게 해야함.
    val visit = Array(row,{Array(col,{false})})
    var origin = b.size-list.size
    val tempQueue : Queue<Pair<Int,Int>> = LinkedList()
    for(queue in q){
        tempQueue.add(queue)
    }
    var tempArray = array.copyOf()
    for(l in list)
        tempArray[l.first][l.second]=1
    while(!tempQueue.isEmpty()){
        val now = tempQueue.poll()
        visit[now.first][now.second]=true
        for(i in 0 until 4){
            val mx = now.first+x[i]
            val my = now.second+y[i]
            if(mx<0 || my < 0 || mx>=row || my>=col)
                continue
            if(tempArray[mx][my]==1 || visit[mx][my] || tempArray[mx][my]==2) //벽이나  바이러스는 안들어감.
                continue
            origin--
            tempArray[mx][my]=2
            tempQueue.add(Pair(mx,my))
        }
    }
    for(l in b)
        array[l.first][l.second]=0
    return origin
}