<백준> 로봇 청소기(Gold 5)

[깃허브]

https://github.com/heesoo-park/ForCodeKata/tree/main/baekjoon%20%EB%AC%B8%EC%A0%9C%EC%A7%91/%EB%A1%9C%EB%B4%87%20%EC%B2%AD%EC%86%8C%EA%B8%B0

[백준]

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

제출 결과

 

정답 비율이 50퍼가 넘는 문제여서 그런지 생각보다 쉽게 풀었다.

문제에 조건이 많았지만 순서대로 진행하면 풀리더라

 

나는 계속 로봇 청소기가 쭉쭉 움직이면서 더 이상 청소 못할 때까지 작동하는 걸 보고 DFS가 생각나더라(이게 코딩하는 사람의 마음인가...?)

그래서 가장 먼저 DFS로 도전했고 어떻게 DFS를 짰었는지 생각이 안 나서 예전에 풀었었던 DFS문제들을 보며 재활훈련을 잠시 했다.

그런데 그 때랑 조금 다르게 접근한건 visited배열을 사용하지 않았다는 것이다.

그냥 주어진 2차원 배열 값을 변경시키면서 해결했다.

모든 입력값은 전역으로 받아 다른 함수들에서도 편하게 값을 변경했다.

이렇게 할 수 있었던 것은 DFS이지만 깊숙히 들어갔다가 다시 돌아오는 케이스가 없었기 때문이었다.

 이런 측면에서 본다면 DFS 안 쓰고 반복문을 썼어도 됐을 거 같기는 하다.

 

가장 큰 분기점은 주변 4칸에 청소가 안 된 곳이 있는가여서 따로 함수를 만들었다.

그리고 그 안의 세부 조건은 when문으로 처리했다.

좀 많이 길어지긴 했지만... 

그렇다고 어떻게 묶을 방법이 보이지가 않았다.

 

그렇게 0인 자리에 도착하면 count를 올리는 것으로 문제는 해결했고 한번에 통과했다.

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.util.StringTokenizer

var count = 0
var n = 0
var m = 0
var r = 0
var c = 0
var d = 0
var room = Array(50) { Array(50) { 0 } }
fun main() = with(System.`in`.bufferedReader()) {
    with(StringTokenizer(readln())) {
        n = nextToken().toInt()
        m = nextToken().toInt()
    }

    with(StringTokenizer(readln())) {
        r = nextToken().toInt()
        c = nextToken().toInt()
        d = nextToken().toInt()
    }

    for (i in 0 until n) {
        with(StringTokenizer(readln(), " ")) {
            for (j in 0 until m) {
                room[i][j] = nextToken().toInt()
            }
        }
    }

    solve()
    println(count)
}

fun checkClean(): Boolean {
    return room[r + 1][c] != 0 && room[r][c + 1] != 0 && room[r - 1][c] != 0 && room[r][c - 1] != 0
}

fun solve() {
    if (room[r][c] == 0) {
        room[r][c] = -1
        ++count
    }

    if (checkClean()) {
        when (d) {
            0 -> {
                if (room[r + 1][c] == 1) {
                    return
                } else {
                    r += 1
                }
            }
            1 -> {
                if (room[r][c - 1] == 1) {
                    return
                } else {
                    c -= 1
                }
            }
            2 -> {
                if (room[r - 1][c] == 1) {
                    return
                } else {
                    r -= 1
                }
            }
            3 -> {
                if (room[r][c + 1] == 1) {
                    return
                } else {
                    c += 1
                }
            }
        }
        solve()
    } else {
        d = when (d) {
            0 -> {
                if (room[r][c - 1] == 0) c -= 1
                3
            }
            1 -> {
                if (room[r - 1][c] == 0) r -= 1
                0
            }
            2 -> {
                if (room[r][c + 1] == 0) c += 1
                1
            }
            3 -> {
                if (room[r + 1][c] == 0) r += 1
                2
            }
            else -> -1
        }
        solve()
    }
}