[백준/BOJ] 16956번: 늑대와 양

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

16956번: 늑대와 양

문제

크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 이동할 수 있다. 두 칸이 인접하다는 것은 두 칸이 변을 공유하는 경우이다.

목장에 울타리를 설치해 늑대가 양이 있는 칸으로 갈 수 없게 하려고 한다. 늑대는 울타리가 있는 칸으로는 이동할 수 없다. 울타리를 설치해보자.

입력

첫째 줄에 목장의 크기 R, C가 주어진다.

둘째 줄부터 R개의 줄에 목장의 상태가 주어진다. '.'는 빈 칸, 'S'는 양, 'W'는 늑대이다.

출력

늑대가 양이 있는 칸으로 갈 수 없게 할 수 있다면 첫째 줄에 1을 출력하고, 둘째 줄부터 R개의 줄에 목장의 상태를 출력한다. 울타리는 'D'로 출력한다. 울타리를 어떻게 설치해도 늑대가 양이 있는 칸으로 갈 수 있다면 첫째 줄에 0을 출력한다.

해설

양과 늑대과 인접하고 있다면 울타리를 어떻게 놓든 늑대는 양에 있는 칸으로 움직일 수 있다.

따라서 0을 출력한다.

 

둘이 인접하고 있지 않다면 양의 동서남북으로 해서 울타리를 치면 된다.또는 .를 모두 D로 바꾸어도 된다.

소스 코드

lateinit var field: Array<CharArray>
val dx = arrayOf(0, 0, 1, -1)
val dy = arrayOf(1, -1, 0, 0)

fun main() = with(System.`in`.bufferedReader()) {
    val (r, c) = readLine().split(" ").map { it.toInt() }
    field = Array(r) { CharArray(c) { '.' } }
    repeat(r) { i ->
        val input = readLine()
        repeat(c) { j ->
            field[i][j] = input[j]
        }
    }
    bfs(r, c)
}

fun bfs(r: Int, c: Int) {
    for(i in 0 until r) {
        for(j in 0 until c) {
            if(field[i][j] == 'S') {
                for(k in 0 until 4) {
                    val ny = i + dy[k]
                    val nx = j + dx[k]
                    if(ny < 0 || nx < 0 || ny >= r || nx >= c) continue
                    if(field[ny][nx] == 'W') {
                        println(0)
                        return
                    }
                    else if(field[ny][nx] == '.') field[ny][nx] = 'D'
                }
            }
        }
    }
    println(1)
    for(i in 0 until r) {
        for(j in 0 until c) {
            print(field[i][j])
        }
        println()
    }
}