[백준/BOJ] 14503번: 로봇 청소기

문제

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

14503번: 로봇 청소기

해설

처음 문제를 해결하려 할 때 방향에 대해서 헷갈렸지만 별거 없는 것이었다.

"바라보고 있는 방향의 왼쪽에 청소하지 않은 칸이 있다면  그 칸으로 이동한다".

즉, 내가 북쪽을 보고 있을 때, 서쪽을 보고 청소가 되있지 않다면 청소하러 가라인 것이다.

 

다음으로 4칸이 모두 벽과 청소한 구역으로 이루어져 있어 이동할 수 없는 경우 방향을 유지한 채로 뒤로 한칸 간다.

이때 뒤의 방향이 벽이라면 이동할 수 없지만, 청소를 한 구역은 이동할 수 있다는 것이다.

 

결론적으로는 현재 위치 청소를 청소한 후, 왼쪽 방향을 확인하여 청소를 한 구역이라면 그 방향으로 회전, 아직 안한 구역이라면 그 방향으로 회전 후 1칸 전진을 한다. 만약 4칸 모두 청소할 구역이 없을 때, 뒤가 청소한 구역이라면 뒤로 가고, 벽이라면 종료하면 된다.

코드

private var row = 0
private var col = 0
private lateinit var map: Array<IntArray>
private val dir = arrayOf(-1 to 0, 0 to 1, 1 to 0, 0 to -1)
private var cleanArea = 0

fun main() = with(System.`in`.bufferedReader()) {
    val input = readLine().split(" ").map { it.toInt() }
    row = input[0]
    col = input[1]

    map = Array(row) { IntArray(col) }

    val (curY, curX, direction) = readLine().split(" ").map { it.toInt() }

    repeat(row) { i ->
        val state = readLine().split(" ").map { it.toInt() }
        repeat(col) { j ->
            map[i][j] = state[j]
        }
    }

    cleanArea++
    dfs(curY, curX, direction)

    println(cleanArea)
}

private fun dfs(y: Int, x: Int, direction: Int) {
    map[y][x] = -1

    repeat(4) {
        val nextDir = (direction + 3 - it) % 4
        val nextY = y + dir[nextDir].first
        val nextX = x + dir[nextDir].second

        if(isCondition(nextY, nextX) && map[nextY][nextX] == 0) {
            cleanArea++
            dfs(nextY, nextX, nextDir)
            return
        }
    }

    val backDirection = (direction + 2) % 4
    val backY = y + dir[backDirection].first
    val backX = x + dir[backDirection].second

    if(isCondition(backY, backX) && map[backY][backX] != 1) {
        dfs(backY, backX, direction)
    }
}


private fun isCondition(y: Int, x: Int): Boolean = y in 0 until row && x in 0 until col