#17070 파이프 옮기기 1

문제

---

 

코드

---

enum class Direction {
    HORIZONTAL, VERTICAL, DIAGONAL
}

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val house = Array(n) { IntArray(n) }
    var count = 0
    repeat(n) { i ->
        house[i] = readLine().split(' ').map { it.toInt() }.toIntArray()
    }

    fun dfs(h: Int, v: Int, prevDir: Direction) {
        if (h >= n || v >= n || house[h][v] == 1) return
        // 대각선은 3칸을 차지하기 때문에 추가적으로 확인
        if (prevDir == Direction.DIAGONAL && (house[h - 1][v] == 1 || house[h][v - 1] == 1)) return
        if (h == n - 1 && v == n - 1) {
            count++
            return
        }
        when (prevDir) {
            Direction.HORIZONTAL -> {
                // 가로, 대각선
                dfs(h, v + 1, Direction.HORIZONTAL)
                dfs(h + 1, v + 1, Direction.DIAGONAL)
            }

            Direction.VERTICAL -> {
                // 세로, 대각선
                dfs(h + 1, v, Direction.VERTICAL)
                dfs(h + 1, v + 1, Direction.DIAGONAL)
            }

            Direction.DIAGONAL -> {
                // 가로, 세로, 대각선
                dfs(h, v + 1, Direction.HORIZONTAL)
                dfs(h + 1, v, Direction.VERTICAL)
                dfs(h + 1, v + 1, Direction.DIAGONAL)
            }

        }
    }
    dfs(0, 1, Direction.HORIZONTAL)
    println(count)
}

 

풀이

---

우선 각각의 케이스가 가능한지 확인하기 위해서 dfs로 탐색하는 것이 좋겠다고 생각했다.

 

그리고 이전에 파이프를 위치시켜놓은 방향에 따라서 파이프를 옮길 수 있는 방향이 달라지기 때문에 이전 방향을 dfs의 인자로 받도록 했다.

그리고 현재 위치에 파이프를 놓는 것이 가능한지 확인하는 if문 두개를 추가했다.

여기서 주의할 점은 가로, 세로 방향은 한 칸만 벽이 있는 지 확인하면 되는데, 대각선은 3칸을 확인해야 해서 아래 if문이 하나 추가된 것

그리고 옮기고자 하는 위치가 되면 해당 루트가 가능하다는 것이기 때문에 count를 증가시킴

 

처음에 한 번 틀렸었는데, 이유가 if문의 순서 때문이었다.

가장 처음에 최종 위치인지 확인하는 if문을 작성하고, 아래 return 을 위한 if문 2개를 작성했었는데, 이렇게 되면 불가능한 케이스에서도 count를 할 가능성이 있기 때문에 틀린 풀이가 된다.

 

이 문제를 dp로도 풀 수 있더라. 처음에 dp로 풀 수 있을 것 같아서 dp로 풀려고 하다가 dfs가 더 쉬울 것 같아서 dfs로 풀었다.

다른 사람들의 풀이를 보니 dp로 풀면 3차원 배열을 사용하더라. 아마 enum을 사용하면 2차원 배열도 가능할 것 같다