백준 2665 미로만들기 Kotlin (다익스트라)

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

2665번: 미로만들기

문제

n×n 바둑판 모양으로 총 n2개의 방이 있다. 일부분은 검은 방이고 나머지는 모두 흰 방이다. 검은 방은 사면이 벽으로 싸여 있어 들어갈 수 없다. 서로 붙어 있는 두 개의 흰 방 사이에는 문이 있어서 지나다닐 수 있다. 윗줄 맨 왼쪽 방은 시작방으로서 항상 흰 방이고, 아랫줄 맨 오른쪽 방은 끝방으로서 역시 흰 방이다.

시작방에서 출발하여 길을 찾아서 끝방으로 가는 것이 목적인데, 아래 그림의 경우에는 시작방에서 끝 방으로 갈 수가 없다. 부득이 검은 방 몇 개를 흰 방으로 바꾸어야 하는데 되도록 적은 수의 방의 색을 바꾸고 싶다.

아래 그림은 n=8인 경우의 한 예이다.

위 그림에서는 두 개의 검은 방(예를 들어 (4,4)의 방과 (7,8)의 방)을 흰 방으로 바꾸면, 시작방에서 끝방으로 갈 수 있지만, 어느 검은 방 하나만을 흰 방으로 바꾸어서는 불가능하다. 검은 방에서 흰 방으로 바꾸어야 할 최소의 수를 구하는 프로그램을 작성하시오.

단, 검은 방을 하나도 흰방으로 바꾸지 않아도 되는 경우는 0이 답이다.

입력

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

출력

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

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 데이크스트라

풀이

다익스트라 문제.

하지만 priority queue만 사용했다 뿐이지 사실 visited를 boolean으로 두어도 된다.

무슨 말이냐면 일반적인 다익스트라는 매 칸에 방문하는 최소 가중치를 갱신하고, 해당 칸에 도착했을 때 최소 가중치 이상이면 탐색을 스킵하지만, 이 문제는 매 칸에 그냥 방문 여부만 저장하고 방문했다면 탐색을 스킵해도 통과된다.

아무튼 일반적인 다익스트라로 풀면 끝..! 기본 다익스트라 문제라 따로 풀이할 내용은 없다.

다익스트라 풀이는 다음과 같다.

1. 현재 탐색할 노드의 cnt가 그래프에 기록된 cnt보다 크다면 스킵

2. 현재 노드에서 인접4방향에 대해 이동

3. 이동한 칸이 그래프를 벗어난다면 스킵

4. 이동한 칸이 '0'이라면 cnt를 증가시킨다.

5. 현재 노드에서 이동한 경우의 cnt가 그래프에 기록된 cnt와 같거나 크다면 스킵

6. 위 조건드렝 해당하지 않는다면 해당 칸에 cnt를 기록하고 pq에 추가하여 탐색을 이어나간다. 

 

 

코드

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getStr() = br.readLine().trim()
fun getInt() = br.readLine().trim().toInt()

data class Node(
    val cnt: Int,
    val r: Int,
    val c: Int
)

val dir = arrayOf(
    arrayOf(0,1),
    arrayOf(1,0),
    arrayOf(0,-1),
    arrayOf(-1,0)
)

fun main() = with(System.out.bufferedWriter()){
    //input
    val n = getInt()
    val graph = Array(n){ getStr() }
    //solve
    //output
    write("${bfs(n,graph)}")
    close()
}
fun bfs(n: Int, graph: Array<String>): Int{
    val pq =  PriorityQueue<Node>(compareBy<Node> { it.cnt })
    pq.add(Node(0,0,0))
    val visited = Array(n){IntArray(n){Int.MAX_VALUE}}
    visited[0][0] = 0
    while(pq.isNotEmpty()){
        val (cnt, cr, cc) = pq.poll()
        if(cnt > visited[cr][cc]) continue
        for(i in 0 until 4){
            val nr = cr + dir[i][0]
            val nc = cc + dir[i][1]
            if(nr !in 0 until n || nc !in 0 until n) continue
            val nCnt = if(graph[nr][nc] =='0') cnt+1 else cnt
            if(visited[nr][nc] <= nCnt) continue
            visited[nr][nc] = nCnt
            pq.add(Node(nCnt,nr,nc))
        }
    }
    return visited[n-1][n-1]
}