[Java] 백준(실버-1) 1074번 - Z

문제 풀이

---

이 문제는 분할 정복 재귀를 이용해 풀 수 있는 문제이다.

아이디어 도출

이 문제는 배열을 사분면으로 나누고, 입력받은 R, C의 위치가 몇 번째 사분면에 속하는지 알아내는 것이 중요하다.

1. 입력받은 N을 통해 2의 거듭제곱 N 값으로 배열 한 변의 길이(size)를 구한다.
2. 재귀를 호출하면서 현재 R, C의 위치가 몇 사분면에 속하는지 확인한 후 방문순서를 갱신한다.

   1사분면의 위치라면 방문 순서를 갱신할 필요가 없고, 2사분면일 경우 1사분면의 위치 (size*size)/4 를, 3사분면일 경우 1,2사분면의 모든 위치 ((size*size)/4) * 2를, 4사분면일 경우 1,2,3사분면의 위치 ((size*size)/4) * 3를 모두 더해준다.

3. R, C의 위치가 몇 사분면인지 확인하여 방문 순서를 갱신했다면, R, C의 위치를 찾기 위해 해당 사분면의 시작점으로 배열을 절반씩 줄여가면서 재귀 호출해준다.
4. 위 과정을 반복하면서 길이(size)가 1이 된다면 R, C의 위치를 찾은 것이니 재귀를 종요하고 이전까지 갱신했던 방문순서를 출력하면 된다.

말로 설명하면 이해하기 어려울 수 있으니 예시를 몇 가지 들어보자.

N=3,R=7,C=7일 경우 size=8, newSize=4 이다.
(R>=newSize && C>=newSize) 조건을 만족하기에 4사분면에 속한다.
7행 7열은 63번째로 방문하게 된다.

N=3,R=3,C=7일 경우 size=8, newSize=4 이다.
(R<newSize && C>=newSize) 조건을 만족하기에 2사분면에 속한다.
3행 7열은 31번째로 방문하게 된다.

이때, 1사분면 중 0행 0열은 어차피 0번째로 방문하여 방문 순서가 0번째기에 1사분면 조건에서 방문 순서를 갱신할 필요는 없다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

import java.io.*;
import java.util.*;

class Main {    

    static int result;

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());

        // 분할정복 재귀 문제
        
        // N이 1보다 크다면, NXN 배열을 4사분면으로 두어 재귀로 탐색을 한다.
        // N=2이면 4X4, N=3이면 8X8 배열이 된다.

        // 1,2,3,4 사분면을 탐색하며 R, C가 어디범위에 속해있는지 확인한다.
        // R, C의 사분면이 어디인지 파악했다면, 해당 사분면만 재귀 호출을 한다.
        // size를 절반씩 나눠가면서 해당 사분면에서 R, C 값을 찾아간다.
        // size가 1이 된다면 R,C를 찾은 것이기에 값을 저장하고 return 하면 된다.

        // 배열의 크기를 2의 N승 형태의 거듭제곱으로 정한다.
        // 즉 여기서의 size는 한 변의 길이가 된다.
        int size = (int) Math.pow(2, N);

        result = 0;
        // 재귀함수를 통해 result에 방문 순서를 갱신한다.
        recursion(R, C, size);

        // 갱신된 방문 순서가 담긴 result를 출력한다.
        bw.write(result+"\n");
        
        bw.close();
        br.close();
    }

    /**
     * 사분면을 탐색해가며 R,C를 찾을 재귀함수
     */
    static void recursion(int R, int C, int size) {
        
        // 가장 작은 단위로 사분면을 쪼개어 
        if(size == 1) {
            return;
        }
        
        // R,C의 위치가 어떤 사분면인지 확인하기 위해 배열을 절반으로 줄인다.
        int newSize = size / 2;

        /**
         * 특정 사분면 파악
         * 1사분면: R < newSize 그리고 C < newSize
         * 2사분면: R < newSize 그리고 C >= newSize 
         * 3사분면: R >= newSize 그리고 C < newSize
         * 4사분면: R >= newSIze 그리고 C >= newSize
         * 
         * 방문 순서
         * R과 C의 위치가 1사분면이면 방문 순서를 기록하지 않았기에 그대로 둔다.
         * R과 C의 위치가 2사분면이라면, 1 사분면을 모두 방문해야 하므로 result에 (size * size / 4) 값을 더해준다.
         * R과 C의 위치가 3사분면이라면, 1,2 사분면을 모두 방문해야 하므로 result에  (size * size / 4 * 2) 값을 더해준다.
         * R과 C의 위치가 4사분면이라면, 1,2,3 사분면을 모두 방문해야 하므로 result에 (size * size / 4 * 3) 값을 더해준다.
         */

        if(R < newSize && C < newSize) { // 1사분면 위치일 경우
            recursion(R, C, newSize);
        }
        else if(R < newSize && C >= newSize) { // 2사분면 위치일 경우
            result += (size * size) / 4;
            recursion(R, C-newSize, newSize);
        }
        else if(R >= newSize && C < newSize) { // 3사분면 위치일 경우
            result += ((size * size) / 4) * 2;
            recursion(R-newSize, C, newSize);

        }
        else if(R >= newSize && C >= newSize) { // 4사분면 위치일 경우
            result += ((size * size) / 4) * 3;
            recursion(R-newSize, C-newSize, newSize);
        }

    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.