[백준/BOJ] 14890번: 경사로

문제

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

14890번: 경사로

해설

문제를 이해하는건 어렵지 않았지만, 코드를 짜고보니 깔끔한 코드가 아닌 것 같은 생각이 들었다. 한 클래스에 한 개의 책임만 지게 하고 싶었지만, 어떻게 나눠야 효율적일지 좀 더 생각을 해봐야겠다.

문제를 풀기 위해 생각해낸 순서는 다음과 같다.

• 각 높이를 입력받을 board 배열, 경사로를 놓았는지 검사할 check 배열을 선언한다.
• 가로로 길을 통과할 수 있는지, 세로로 길을 통과할 수 있는지 확인한다.
  • 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 닿아야한다.
    • 즉, 경사로를 놓는 칸의 높이는 같아야 한다는 것을 알 수 있다.
  • 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
• 경사로는 낮은 칸에 놓으므로 왼쪽과 오른쪽이 있을 때, 왼쪽이 더 낮다면 left - slopeLen부터 left까지의 높이가 같은지 확인해야 하며, 반대일 시 right부터 right + slopeLen의 높이가 같은지 확인해야 한다.
• 이미 경사로를 놓은 칸이라면 또 놓을 수 없다.
• 각각의 조건들을 모두 만족한다면 cnt를 증가시킨다.
• 가로 세로 각각 통과할 수 있는 길을 구해 반환하여 출력한다.

이와 같은 과정을 거쳐 문제를 해결할 수 있었다.

리펙토링을 거쳐 더 나은 코드로 작성해봐야겠다.

코드

import kotlin.math.abs

private lateinit var board: Array<IntArray>
private lateinit var check: Array<BooleanArray>

fun main() {
    val (n, slopeLength) = readLine()!!.split(" ").map { it.toInt() }
    initArr(n)

    var total = canRowPass(n, slopeLength) + canColPass(n, slopeLength)
    println(total)
}

fun initArr(n: Int) {
    board = Array(n) { IntArray(n) }
    check = Array(n) { BooleanArray(n) }

    repeat(n) { i ->
        val heights = readLine()!!.split(" ").map { it.toInt() }
        repeat(n) { j ->
            board[i][j] = heights[j]
        }
    }
}

fun canRowPass(n: Int, slopeLength: Int): Int {
    var cnt = 0

    for(i in 0 until n) {
        var canPass = true

        var start = 0
        var end = 1
        while(start != n - 1) {
            if(board[i][start] == board[i][end]) {
                start++
                end++
            }
            else {
                if(abs(board[i][start] - board[i][end]) != 1) {
                    canPass = false
                    break
                }

                if(board[i][start] > board[i][end]) {
                    if(end + slopeLength - 1 >= n) {
                        canPass = false
                        break
                    }

                    for(j in end until end + slopeLength) {
                        if(check[i][j] || board[i][end] != board[i][j]) {
                            canPass = false
                            break
                        }
                    }

                    if(canPass) {
                        for(j in end until end + slopeLength) {
                            check[i][j] = true
                        }
                        start = end + slopeLength - 1
                        end = start + 1
                    }
                }
                else {
                    if(start - slopeLength + 1 < 0) {
                        canPass = false
                        break
                    }

                    for(j in start - slopeLength + 1 .. start) {
                        if(check[i][j] || board[i][start] != board[i][j]) {
                            canPass = false
                            break
                        }
                    }

                    if(canPass) {
                        for(j in start - slopeLength + 1 .. start) {
                            check[i][j] = true
                        }
                        start = end
                        end = start + 1
                    }
                }
            }
            if(!canPass) break
        }
        if(canPass) cnt++
    }
    return cnt
}

fun canColPass(n: Int, slopeLength: Int): Int {
    check = Array(n) { BooleanArray(n) }
    var cnt = 0

    for(i in 0 until n) {
        var canPass = true

        var start = 0
        var end = 1
        while(start != n - 1) {
            if(board[start][i] == board[end][i]) {
                start++
                end++
            }
            else {
                if(abs(board[start][i] - board[end][i]) != 1) {
                    canPass = false
                    break
                }

                if(board[start][i] > board[end][i]) {
                    if(end + slopeLength - 1 >= n) {
                        canPass = false
                        break
                    }

                    for(j in end until end + slopeLength) {
                        if(check[j][i] || board[end][i] != board[j][i]) {
                            canPass = false
                            break
                        }
                    }

                    if(canPass) {
                        for(j in end until end + slopeLength) {
                            check[j][i] = true
                        }
                        start = end + slopeLength - 1
                        end = start + 1
                    }
                }
                else {
                    if(start - slopeLength + 1 < 0) {
                        canPass = false
                        break
                    }

                    for(j in start - slopeLength + 1 .. start) {
                        if(check[j][i] || board[start][i] != board[j][i]) {
                            canPass = false
                            break
                        }
                    }

                    if(canPass) {
                        for(j in start - slopeLength + 1 .. start) {
                            check[j][i] = true
                        }
                        start = end
                        end = start + 1
                    }
                }
            }
            if(!canPass) break
        }
        if(canPass) cnt++
    }
    return cnt
}