[백준 15685번] [Kotlin] 드래곤 커브

 

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

15685번: 드래곤 커브

 

난이도 : 골드 3
태그 : 구현, 시뮬레이션

 

 

설명

 

지렁이를 그냥 그려놓은 것 같지만, 잘 보다보면 규칙성을 찾을 수 있습니다.

 

 

 

0세대를 봅시다. → 방향입니다.

 

 

1세대 입니다. 0세대의 →를 90도 회전한 ↑ 방향입니다.

 

 

2세대입니다. 1세대는 →↑였습니다.

↑를 90도 회전하여 ←,

→를 90도 회전하여 ↑가 되었습니다.

 

 

슬슬 규칙성이 보이시나요? 저는 한참을 계속 봤던 것 같습니다.

2세대는 →↑←↑ 였습니다.

맨 끝 부터 역순으로 90도씩 회전해보겠습니다.

↑←↑→

←↓←↑ 

k번째 세대의 드래곤 커브의 경우, k-1 번째의 마지막 드래곤 커브부터 시작해 역순으로 탐색하며 90도 돌려 이어붙이면 됩니다.

 

 

즉 방향 d의 다음 방향 nd는 (d+1) % 4가 됩니다!

 

 

그럼, 네 꼭짓점이 모두 드래곤 커브의 일부인지는 어떻게 알까요?

var countSquare = 0
for (i in 0..<100) {
    for (j in 0..<100) {
        if (map[i][j] && map[i][j + 1] && map[i + 1][j] && map[i + 1][j + 1]) {
            countSquare++
        }
    }
}

 

저 같은 경우, 100 x 100 boolean 배열을 생성해놓고 드래곤 커브의 일부인 지역은 true 처리를 해놓았는데요.

단순히 점(i, j)에 대해 (i, j), (i, j+1), (i+1, j), (i+1, j+1)이 모두 true인지 확인하면 됩니다.

 

 

 

소스코드

val dx = intArrayOf(0, -1, 0, 1)
val dy = intArrayOf(1, 0, -1, 0)

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val map = Array(101) { BooleanArray(101) }

    repeat(n) {
        var (y, x, d, g) = readLine().split(" ").map { it.toInt() }
        val list = ArrayList<Int>()

        list.add(d)
        map[x][y] = true
        x += dx[d]
        y += dy[d]
        map[x][y] = true

        repeat(g) {
            for (i in list.size - 1 downTo 0) {
                val nd = (list[i] + 1) % 4
                x += dx[nd]
                y += dy[nd]

                map[x][y] = true
                list.add(nd)
            }
        }
    }

    var countSquare = 0
    for (i in 0..<100) {
        for (j in 0..<100) {
            if (map[i][j] && map[i][j + 1] && map[i + 1][j] && map[i + 1][j + 1]) {
                countSquare++
            }
        }
    }

    println(countSquare)
}

 

드래곤 커브를 진행하며 지나온 점들을 모두 List에 넣어주면서,

다음 세대의 드래곤 커브를 진행할 때엔 역순으로 탐색하며 (방향+1) % 4의 방향으로 드래곤 커브를 진행합니다.

 

 

문제의 방향과 같이 dx, dy를 선언할 경우 index를 +1 함으로써 방향을 90도 튼 것과 같은 효과를 얻을 수 있기 때문입니다.

 

 

 

후기

뭐 이런 문제가 다 있지 싶었는데... 삼성 기출문제더라고요.

새로운 유형에 당황했던 것 같습니다.