백준 - 경쟁적 감염

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://www.acmicpc.net/problem/18405

 

[문제 설명]

우선도가 높은 바이러스부터 퍼지게 해라

[접근 방법]

우선도가 높은 바이러스들부터 차례대로 큐에 넣고 BFS로 주변을 감염시키면 된다.

 

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.LinkedList

val dy = intArrayOf(-1,0,1,0)
val dx = intArrayOf(0,1,0,-1)
lateinit var map: Array<IntArray>
data class Virus(val noOfVirus: Int, val row: Int, val col: Int)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    // 바이러스를 담을 리스트
    val listOfVirusPosition = ArrayList<Virus>()
    val (N, K) = readLine().split(" ").map{it.toInt()}
    map = Array(N){ IntArray(N) }

    repeat(N) { row ->
        var col = 0
        readLine().split(" ").map { it.toInt() }.forEach { noOfVirus ->
            if (noOfVirus != 0) {
                listOfVirusPosition.add(Virus(noOfVirus = noOfVirus, row = row, col = col))
                map[row][col] = noOfVirus
            }
            col++
        }
    }

    val queue = LinkedList<Virus>()
    // 바이러스 종류 순서대로 정렬
    listOfVirusPosition.sortedWith { o1, o2 -> o1.noOfVirus - o2.noOfVirus }.forEach { virus ->
        queue.offer(virus)
    }

    val (S, X, Y) = readLine().split(" ").map { it.toInt() }
    // S초만큼만 반복
    repeat(S) {
        // 현재 큐에 있는 모든 바이러스를 전염시켜야함
        val sizeOfQ = queue.size
        repeat(sizeOfQ) {
            val virus = queue.poll()
            for (idxDirection in 0..3) {
                val nextRow = virus.row + dy[idxDirection]
                val nextCol = virus.col + dx[idxDirection]

                // 다음 좌표가 맵 밖으로 나가지 않는다면
                if (nextRow in 0 until N && nextCol in 0 until N) {
                    // 이미 감염된 블록이 아니면
                    if (map[nextRow][nextCol] == 0) {
                        // 감염시키고 현재 블록부터 다시 감염시켜야하므로 큐에 넣어줌
                        map[nextRow][nextCol] = virus.noOfVirus
                        queue.offer(Virus(noOfVirus = virus.noOfVirus, row = nextRow, col = nextCol))
                    }
                }
            }
        }
    }

    println(map[X-1][Y-1])
}