(BOJ) 1074 Z

1074 Z

• 분류 : 분할정복, 재귀

문제

한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다.

예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

N > 1인 경우, 배열을 크기가 2^(N-1) × 2^(N-1)로 4등분 한 후에 재귀적으로 순서대로 방문한다.

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

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

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

입력

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

출력

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

제한

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

예제 입력 1

2 3 1

예제 출력 1

11

예제 입력 2

3 7 7

예제 출력 2

63

예제 입력 3

1 0 0

예제 출력 3

0

예제 입력 4

4 7 7

예제 출력 4

63

예제 입력 5

10 511 511

예제 출력 5

262143

예제 입력 6

10 512 512

예제 출력 6

786432

Solution

펼쳐보기

import java.util.*

private var N: Int = 0
private var R: Int = 0
private var C: Int = 0

fun main() {
    input()
    solve()
}

private fun input() = with(Scanner(System.`in`)) {
    N = nextInt()
    R = nextInt()
    C = nextInt()
}

private fun solve() {
    val side = 2.pow(N) // 분할정복할 한 변의 길이

    divide(side, R, C)
    println(conquer(0))
}

private fun divide(side: Int, row: Int, column: Int) {
    if (side == 1) {
        return
    }

    // 목표 좌표가 1사분면 안쪽에 있음
    if (row < side / 2 && column < side / 2) {
        conquer(0) // 가중치 없음
        divide(side / 2, row, column)
    }
    // 목표 좌표가 2사분면에 있음
    else if (side / 2 in (row + 1)..column) {
        conquer(side * side / 4) // 1사분면에 해당하는 만큼 가중치 추가
        divide(side / 2, row, column - side / 2)
    }
    // 목표 좌표가 3사분면에 있음
    else if (side / 2 in (column + 1)..row) {
        conquer(side * side / 4 * 2) // 2사분면에 해당하는 만큼 가중치 추가
        divide(side / 2, row - side / 2, column)
    }
    // 목표 좌표가 4사분면에 있음
    else {
        conquer(side * side / 4 * 3) // 3사분면에 해당하는 만큼 가중치 추가
        divide(side / 2, row - side / 2, column - side / 2)
    }
}

private var result = 0
private fun conquer(coefficient: Int): Int {
    result += coefficient
    return result
}

fun Int.pow(n: Int): Int {
    return Math.pow(this.toDouble(), n.toDouble()).toInt()
}

Point of Thinking

• 분할 정복의 대표적인 예시인 색종이 자르기의 응용인 버전이다.
• 주어진 배열을 기준으로 주어진 좌표가 몇 사분면에 위치하는지 분기하면서 계속해서 분할해나간다.
• 분할하면서 순회할 필요가 없는 사분면의 면적값(=순회 횟수)를 더해나가면서 더해나간다(=정복).
• N이 1일 될때까지 순회 후 정복한 값을 출력하면 Accpeted.

References

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