백준 1074번 Z :: 마이구미

이 글은 백준 알고리즘 문제 1074번 "Z" 을 풀이한다.

풀이 방법으 말하자면, 분할 정복 알고리즘이다.

분할 정복이란, 문제를 작은 부분으로 쪼개어 해결하는 방식이다.

문제 링크 - https://www.acmicpc.net/problem/1074

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

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

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

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

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

본인은 문제를 정확하게 이해하지 않아, 꽤 고생한 문제이다.

문제의 규칙을 이해를 한다면, 어렵지 않다.

중요한 것은 2가지가 된다.

1. 4등분한다.
2. Z 형태의 순서로 방문한다.

위 2가지는 크기와 상관없이 항상 적용된다.

이것이 의미하는 그림은 다음과 같다. (N = 4)

위를 토대로 알 수 있는 것은 찾는 좌표가 어느 분면에 속하는 지 알아내면 문제를 해결할 수 있다.

예시를 통해 확인하면 쉽게 이해할 수 있다. (N = 4)

위의 빨간색의 Z에 속한 좌표를 찾는다고 가정해보자.

3분면에 속한다는 것을 알 수 있다.

3분면에 속한다는 의미는 1, 2분면을 방문했다는 것을 의미한다.

그렇다는건 결국 1, 2분면의 방문한 수를 더해주면 된다.

그 후, 3분면 안에서 다시 4등분으로 나눌 수 있다.

나눈 후 4분면에 속한다는 것을 알 수 있다.

4분면에 속하기 때문에, 1, 2, 3분면을 방문한 수를 더해주면 된다.

이렇게 다음 영역에서 4등분하는 과정을 반복해주면 된다.

 

이렇게 작은 부분으로 분할해서 접근하면 문제를 해결할 수 있다.

접근 방식만 파악한다면, 구현에서의 어려운 부분은 없다.

자세한 건 코드를 통해 확인하면 된다.

Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/divide-conquer/1074.java

private void solve() {
    int n = sc.nextInt();
    int r = sc.nextInt();
    int c = sc.nextInt();
    int ans = 0;
    int y = (int) Math.pow(2, n) / 2;
    int x = y;
 
    while (n-- > 0) {
        int temp = (int) Math.pow(2, n) / 2;
        int skip = (int) Math.pow(4, n);
 
        if (r < y && c < x) {
            // 1
            x -= temp;
            y -= temp;
        } else if (r < y && x <= c) {
            // 2
            x += temp;
            y -= temp;
            ans += skip;
        } else if (y <= r && c < x) {
            // 3
            x -= temp;
            y += temp;
            ans += skip * 2;
        } else {
            // 4
            x += temp;
            y += temp;
            ans += skip * 3;
        }
    }
    System.out.println(ans);
}