• 백준 1074번 Z :: 마이구미
    알고리즘 풀이/분할 정복 2018. 1. 26. 21:15
    반응형

    이 글은 백준 알고리즘 문제 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)


    1074번 Z1074번 Z


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

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


    1074번 Z


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

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

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

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


    1074번 Z


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

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


    1074번 Z


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

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


    1074번 Z

     

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

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

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


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


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    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);
    }
    cs


    반응형

    '알고리즘 풀이 > 분할 정복' 카테고리의 다른 글

    백준 1074번 Z :: 마이구미  (2) 2018.01.26

    댓글 2

    • 신성 2019.06.22 01:41

      이거 혹시 한번만 설명해주실 수 있나요? 너무 풀고 싶은데 ㅠㅠ 어렵네요..
      x와 y, 또, 왜 나누시는지..

      • Favicon of https://mygumi.tistory.com 마이구미 mygumi 2019.06.29 11:30 신고

        구체적으로 어떤 부분이 이해가 안가실까요...?
        코드보다는 우선 글에 있는 그림들을 이해하셔야할 것 같습니다.
        알려주시면 조금 더 자세히 적어볼게요~

Designed by Tistory.