Today I Learned

오늘은 백준에서 코틀린으로 코테문제를 풀었다.

Z

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

문제

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
다음은 N=3일 때의 예이다.

풀이과정

• 그림을 보면 Z 패턴이 z 모양처럼 반복되는 것을 알 수 있다. 그래서 가로를 절반, 세로를 절반으로 나누면 크게 4사분면이 되는데 이 반복 패턴을 재귀로 구현해서 문제를 풀었다.

1. 입력을 readln().split(" ").map { it.toInt() } 코드로 바로 3개의 변수에 받아 준다.

2. recur() 함수로 재귀 함수를 만든다.

3. 4사분면에서 한 변의 크기는 shl함수로 구해준다. 한 변은 2의 n-1승이므로 1 shl (n-1)로 구한다. 여기서 1은 2의 1승 즉 2를 의미한다.

• shl 함수

  shift left 즉, 이진 표현에서 비트를 왼쪽으로 이동한다.
  val shl shiftAmount 에서
  val을 shiftAmount 만큼 왼쪽으로 비트를 옮긴다는 뜻이다.

4. 주어진 r, c 변수의 숫자에 따라 when으로 0,1,2,3중 몇 사분면에 해당하는지 찾는다.

5. 각 사분면은 이전 사분면 크기의 제곱만큼 크다. 즉, 해당 사분면의 오프셋은 이전 사분면의 크기의 제곱에 현재 사분면의 번호를 곱한 것이다. 이를 이용해 오프셋을 구한다.

6. return에 오프셋만큼 계속 더해주고, 재귀로 recur()함수를 n은 하나 줄이고, r과 c는 halfSize를 차감한 만큼 리턴하면 완료.

Kotlin 코드

fun main() {
    val (n, r, c) = readln().split(" ").map { it.toInt() }
    print(recur(n,r,c))
}

fun recur(n: Int, r: Int, c: Int): Int {
    if (n == 0) return 0

    val halfSize = 1 shl (n - 1)
    val quadrant = when {
        r < halfSize && c < halfSize -> 0
        r < halfSize && c >= halfSize -> 1
        r >= halfSize && c < halfSize -> 2
        else -> 3
    }

    val offset = halfSize * halfSize * quadrant
    return offset + recur(n - 1, r % halfSize, c % halfSize)
}