[백준] 1074 - Z(Java)

문제 파악

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

풀이

재귀적으로 순서대로 방문한다..?
재귀보고 눈이 돌아가서 재귀/큐로 풀었다가 OOM을 만났다 🙂‍↕️

OOM 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int N = (int) Math.pow(2, Integer.parseInt(line[0]));
        int row = Integer.parseInt(line[1]);
        int col = Integer.parseInt(line[2]);
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, N});
        int temp = 0;
        while (!queue.isEmpty()) {
            int[] latest = queue.poll();
            int offset = latest[2] / 2;
            int r = latest[0];
            int c = latest[1];
            if (latest[2] == 1) {
                if (r == row && c == col) {
                    System.out.println(temp);
                    return;
                }
                temp++;
                continue;
            }
            queue.offer(new int[]{r, c, offset});
            queue.offer(new int[]{r, c + offset, offset});
            queue.offer(new int[]{r + offset, c, offset});
            queue.offer(new int[]{r + offset, c + offset, offset});
        }
        System.out.println(-1);
    }
}

그러나 규칙을 찾으면 짧고 쉽게 풀 수 있다
그렇다면,, 규칙을 찾아보도록 하자 🥹

2X2

위 그림을 보면 기본적으로 0 ➡️ 1 ➡️ 2 ➡️ 3 순으로 탐색하는 것을 볼 수 있다.
예시는 2X2 크기의 경우이나 아래의 4X4 경우도 큰 그리드로 보면 동일한 순서를 따른다.

4X4

속한 구역에 따라 미리 탐색한 블럭 개수를 합산해 줄 수 있겠다는 생각이 스친다.

4X4 블럭을 기준으로
0 구역에 속할 경우 앞서 탐색한 블럭이 없을 것이고, 1구역은 4, 2구역은 8개, 3구역은 12개의 고정된 선행 탐색 블럭이 존재한다.
이는 2X2 블럭, 즉 한 구역의 블럭 개수와 동일하다

현재 블럭의 크기를 N으로 두고 정리해 보자면 다음과 같다.

0구역 : 0 + ⍺
1구역 : (N/2) ^ 2 * 1  + ⍺
2구역 : (N/2) ^ 2 * 2 + ⍺
3구역 : (N/2) ^ 2 * 3 + ⍺

⍺에 대해서는 N이 2가 될 때까지 2로 나누어 동일한 규칙으로 연산한다.

또한 탐색 위치는 N이 나눠짐에 따라 상대적으로 바뀌어야 하므로 (r,c) ➡️ (r % (N/2), c % (N/2)) 로 업데이트 해 준다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int N = (int) Math.pow(2, Integer.parseInt(line[0]));
        int row = Integer.parseInt(line[1]);
        int col = Integer.parseInt(line[2]);
        int answer = 0;
        while (N > 1) {
            N /= 2;
            answer += ((row / N) * 2 + col / N) * N * N;
            row %= N;
            col %= N;
        }
        System.out.println(answer);
    }
}