백준 1012번 - 유기농 배추 (코틀린, kotlin)

이번 문제는 간단하게 bfs로 접근할수 있었다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*


val dx = arrayListOf<Int>(0, 1, 0, -1)
val dy = arrayListOf<Int>(1, 0, -1, 0)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val case = readLine().toInt()

    repeat(case) {
        val (M, N, K) = readLine().split(" ").map { it.toInt() }
        val graph = Array(M) { Array(N) { 0 } }
        var answer = 0

        //배추위치찍기
        repeat(K) {
            val (x, y) = readLine().split(" ").map { it.toInt() }
            graph[x][y] = 1
        }

        fun bfs(x: Int, y: Int) {
            var queue = LinkedList<Pair<Int, Int>>()
            queue.offer(Pair(x, y))
            while (!queue.isEmpty()) {
                var cur = queue.poll()

                for (d in 0..3) {
                    val nx = cur.first + dx[d]
                    val ny = cur.second + dy[d]

                    if (nx < 0 || nx >= M || ny < 0 || ny >= N || graph[nx][ny] != 1) continue
                    graph[nx][ny] = 2
                    queue.offer(Pair(nx, ny))
                }
            }

        }

        for (i in 0 until M) {
            for (j in 0 until N) {
                if (graph[i][j] == 1) {
                    bfs(i, j)
                    answer++
                }
            }
        }
        println(answer)
    }
}

앞으로 그래프 문제를 대강 10문제 정도만 풀어보고 다른 알고리즘으로 넘어가야겠다

 

궁금한 사항이 있다면 댓글로 문의해주세요

알고있다면 지식선에서, 모르겠다면 검색해서라도 열심히 답변해드리겠습니다