백준 1074 Z Kotlin (재귀,분할 정복)

문제 출처 : https://www.acmicpc.net/problem/1074

1074번: Z

문제

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2N

알고리즘 분류

• 분할 정복
• 재귀

풀이

사각형의 크기가 1일 때까지 4분할로 나눠가는 재귀 문제이다.

다만 N이 15이기 때문에 N이 10만 돼도 100만 번 이상의 탐색이 필요하다.

따라서 우리는 그래프의 처음부터 r,c가 나올 때까지 탐색을 할 여유는 없고,

r,c가 없을만한 사각형은 그냥 횟수만 더해주고 스킵해야만 시간 내에 r,c를 찾을 수 있다.

 

위의 3 7 7예에서 확인해보자.

가로 세로가 8인 사각형을 4분할 하면 오른쪽 아래에 있는 사각형에 r,c가 존재하는 걸 알 수 있다.

왼위, 왼오, 왼아에 있는 사각형들은 굳이 탐색할 필요가 없으니 이 3개의 사각형의 넓이들을 count에 더해준다.

 

다음 가로 세로가 4인 사각형(위에서 분할한 오아 사각형)을 4분할 하면 이번에도 오른쪽 아래에 있는 사각형에

r,c가 존재하는 걸 알 수 있다. 왼위, 왼오, 왼아에 있는 사각형들의 넓이들을 count에 더해준다.

 

다음 가로 세로가 2인 사각형(위에서 분할한 오아 사각형)을 4분할 하면 이번에도 오른쪽 아래에 있는 사각형에

r,c가 존재하는 걸 알 수 있고, 왼위, 왼오, 왼아에 있는 사각형들의 넓이들을 count에 더해준다.

 

위에서 분할한 오아 사각형의 가로 세로는 1이기 때문에 더 이상 분할을 할 수 없기 때문에 count(방문 순서)를 출력한다.

 

우리는 재귀와 분할 정복을 이용하고, 약간의 그리디한 방식을 통해 r,c에 방문하는 순서를 효율적으로 찾았다.

 

코드(Kotlin)

import java.util.StringTokenizer

var answer = 0
var cnt = 0
fun recurCal(size: Int, rr: Int, cc: Int, r: Int, c: Int) {
    if (rr == r && cc == c) {
        answer = cnt
        return
    }

    if (rr + size > r && rr <= r && cc + size > c && cc <= c) {
        recurCal(size / 2, rr, cc, r, c)
        recurCal(size / 2, rr, cc + size / 2, r, c)
        recurCal(size / 2, rr + size / 2, cc, r, c)
        recurCal(size / 2, rr + size / 2, cc + size / 2, r, c)
    } else {
        cnt += size * size
    }
}

fun main() = with(System.out.bufferedWriter()) {
    with(System.`in`.bufferedReader()){
        val tk =StringTokenizer(readLine())
        var n = Integer.parseInt(tk.nextToken())
        val r = Integer.parseInt(tk.nextToken())
        val c = Integer.parseInt(tk.nextToken())
        var size= 1
        for(i in 0 until n){
            size *=2
        }
        recurCal(size,0,0,r,c)
        write("$answer")
        close()
    }
    close()
}