[Kotlin, B1] 백준 1952번 달팽이2

출처: unsplash.com

 

달팽이 2(1952번)

Bronze 1

#수학 #구현 #시뮬레이션

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

 

문제 내용

 

 

문제 접근

M * N의 2차원 리스트를 시계 방향으로 돌면서 꺾인 지점이 총 몇 개인지 구하는 문제이다.

주의해야 하는 점은 한 번 지난 부분은 다시 지나지 못한다는 것이다.

수학적으로 규칙을 찾아서 해결하는 방법이 있지만, 멍청한 관계로 무지성 전체 탐색을 할 것이다.

 

2차원 리스트를 boolean형으로 생성하면 한 번 지난 부분을 true로 설정하고 조건을 달면 돼서 한 번 지난 부분을 체크할 때 편하다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (h, w) = readLine().split(" ").map { it.toInt() }
    val map = Array(h) { BooleanArray(w) }
    val moveX = listOf(1, 0, -1, 0)
    val moveY = listOf(0, 1, 0, -1)
    var res = 0

    map[0][0] = true

    var currentX = 0
    var currentY = 0
    var m = 0

    while (true) {
        while (currentY in map.indices && currentX in 0 until map[currentY].size) {
            val mx = moveX[m] + currentX
            val my = moveY[m] + currentY

            if (my in map.indices && mx in 0 until map[my].size) {
                if (!map[my][mx]) {
                    map[my][mx] = true

                    currentX = mx
                    currentY = my
                } else break

            } else break
        }

        val afterMove = if (m == 3) 0 else m + 1
        val afterX = currentX + moveX[afterMove]
        val afterY = currentY + moveY[afterMove]

        if (afterY in map.indices && afterX in 0 until map[0].size && !map[afterY][afterX]) {
            res++
            m = afterMove
        } else break
    }

    println(res)
}

 

문제 풀이

입력받은 m, n을 기준으로 2차원 리스트를 생성하고, 이동할 경로를 나타낼 moveX, moveY를 생성한다. moveX, moveY를 순환시키면서 리스트를 순회할 것이다.

 

시작 부분인 0, 0을 true로 지정해 주고, 지정한 move만큼 이동하면서 list의 끝까지 이동한다.

이동하면서 map의 방문 여부도 true로 설정해 준다.

이동하면서 움직인 index는 계속 저장해 준다.

 

끝까지 이동하고 나면 이제 방향을 꺾어야 한다.

꺾을 방향을 afterMove로 move의 index를 지정해 다음에 움직일 방향이 리스트 안에 포함되는지, 그리고 리스트의 방문이 안된 값일 때 꺾은 횟수를 늘려 주고 m을 afterMove로 교체한다.

 

이러면 계속 moveX, moveY에서 설정한 이동 경로에 따라 시계 방향으로 돌게 된다.

 

 

문제 해결 과정

수학적으로 풀면 쉽다. 하지만 안 해봐서 모른다. 하지만 코드가 많이 짧아지고 빠르게 동작할 것이다.

나는 수학적으로 해결하려다가 규칙을 못 찾고 전체 탐색으로 바꿨다.

전체 탐색으로 구현하면 리스트의 방문 여부와 index가 리스트를 벗어나지는 않는지 체크해야 한다. 그래서 구현도 귀찮고 실수가 많이 날 수 있다.