백준 17070 파이프옮기기1

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

(1,1) (2,2)에 가로로 놓여진 파이프를 연결하여 (N,N)까지 이동시키는 방법의 개수를 구하는 문제이다.

파이프는 현재 놓여진 방향에 따라 연결시킬 수 있는 방법이 다르다.

현재 가로로 놓여진 경우 - 또 가로로 or 대각선으로
현재 세로로 놓여진 경우 - 또 세로로 or 대각선으로
현재 대각선으로 놓여진 경우 - 가로, 세로, 대각선 모두 가능

따라서 (2,2)의 가로로 놓여진 상태를 출발점으로, 가로 세로 대각선을 dfs를 통해 직접 놓아 보기로 하였다.

위 내용을 dfs로 설계할 때 주의해야 할 점은 다음과 같다.

1. 현재 방향에 따라 다음 dfs를 호출하는 횟수와 파라미터가 다르다 (대각선이면 3번, 이외 2번)

2. 대각선으로 놓을 때 파이프는 4칸을 차지하므로, 대각선에 놓기 전 4칸 모두 비어 있는지 확인해야 한다.

enum class PipeDir{
    HORIZONTAL,
    VERTICAL,
    DIAGONAL
}

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()
    val field = Array(N){readLine().split(' ').map{it.toInt()}.toTypedArray()}

    var answer = 0
    fun dfs(v: Int, h: Int, pipeDir: PipeDir){
        if(v !in field.indices || h !in field.indices || field[v][h] == 1) return

        if(v == N - 1 && h == N - 1){
            answer++
            return
        }

        when(pipeDir){
            PipeDir.HORIZONTAL -> {
                dfs(v, h + 1, PipeDir.HORIZONTAL)
                if(canPutDiagonal(v, h, field))
                    dfs(v + 1, h + 1, PipeDir.DIAGONAL)
            }
            PipeDir.VERTICAL -> {
                dfs(v + 1, h, PipeDir.VERTICAL)
                if(canPutDiagonal(v, h, field))
                    dfs(v + 1, h + 1, PipeDir.DIAGONAL)
            }
            PipeDir.DIAGONAL -> {
                dfs(v, h + 1, PipeDir.HORIZONTAL)
                dfs(v + 1, h, PipeDir.VERTICAL)
                if(canPutDiagonal(v, h, field))
                    dfs(v + 1, h + 1, PipeDir.DIAGONAL)
            }
        }
    }

    dfs(0, 1, PipeDir.HORIZONTAL)

    print(answer)
}

fun canPutDiagonal(v: Int, h: Int, field: Array<Array<Int>>): Boolean{
    return v + 1 in field.indices && h + 1 in field.indices && field[v+1][h] == 0 && field[v][h+1] == 0
}

1번을 만족시키기에 앞서 방향에 대해 알아보기 쉽도록 하려고 파이프의 방향에 대한 enum class를 정의하였다.

그리고나서 dfs를 y좌표(v), x좌표(h), 현재 파이프의 방향 총 3가지의 파라미터를 추가하여 생성하였다.

dfs는 단순히 현재 파이프의 위치를 기반으로 직접 파이프를 놓아보듯 구현하였다.

파이프를 가로로 놓는 경우 x좌표를 +1시켜 재귀하고, 세로로 놓는 경우 y좌표를 +1시켜 재귀한다.

대각선으로 놓는 경우, 2번 주의할 점을 고려하여 현재 위치가 (x, y)라면 (x+1, y), (x, y+1), (x+1, y+1)이 모두 놓을 수 있는 상태인지 검사하는 canPutDiagonal 함수를 만들어 이용하였다.