[백준] 미로만들기 (2665)(kotlin)

문제 설명

백준 2665번 문제 링크

입력 및 출력

» 입력

첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다.

» 출력

첫 줄에 흰 방으로 바꾸어야 할 최소의 검은 방의 수를 출력한다.

예제 입출력(테스트케이스)

입력	출력
8 11100110 11010010 10011010 11101100 01000111 00110001 11011000 11000111	2

문제 풀이1

import java.util.LinkedList

var N = 0
var matrix = arrayOf<IntArray>()
var check = arrayOf<IntArray>()

fun main(args: Array<String>) = with(System.`in`.bufferedReader()) {
    N = readLine().toInt()
    matrix = Array(N) { IntArray(N) }
    check = Array(N) { IntArray(N) { Int.MAX_VALUE } }

    for (y in 0 until N) {
        val str = readLine()
        for (x in 0 until N) {
            matrix[y][x] = str[x] - '0'
        }
    }


    check[0][0] = 0
    bfs(0, 0)
    println(check[N - 1][N - 1])
}

fun bfs(x: Int, y: Int) {
    val dx = intArrayOf(0,0,1,-1)
    val dy = intArrayOf(1,-1,0,0)

    val q = LinkedList<Pair<Int, Int>>()
    q.add(Pair(0, 0))

    while (q.isNotEmpty()) {
        val now = q.poll()

        for (i in 0 until 4) {
            val nx = now.first + dx[i]
            val ny = now.second + dy[i]

            if (nx !in 0 until N || ny !in 0 until N) continue
            if (check[ny][nx] <= check[now.second][now.first]) continue

            if (matrix[ny][nx] == 1) {
                q.add(Pair(nx, ny))
                check[ny][nx] = check[now.second][now.first]
            } else {
                q.add(Pair(nx, ny))
                check[ny][nx] = check[now.second][now.first] + 1
            }

        }
    }
}