[Python] 백준 1074번 - Z

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

1074번: Z

 

혼자 힘으로 풀었는가?: X

알고리즘 유형
 - 분할 정복
 - 재귀

 

문제

한수는 크기가 \(2^N\) × \(2^N\)인 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\) 

---

앞서 풀었던 분할 정복 문제와 비슷하게 풀어보려고 노력했다.

 

2022.11.24 - [Algorithm/백준] - [Java/Python] 백준 2630번 - 색종이 만들기

[Java/Python] 백준 2630번 - 색종이 만들기

 

그리고 처음에 풀곤 오! 된다! 하는 심정으로 제출을 했다.

 

처음엔 단순히 그림에 그려진 대로 배열을 나눠서 값을 1씩 증가시키는 방법으로 했다.

 

import sys
input = sys.stdin.readline

n, r, c = map(int, input().split())
size = pow(2, n)
data = [ [0] * size for _ in range(size)]

idx = 0
def recursive(row, col, size):
  global idx
  if size == 1:
    data[row][col] = idx
    idx += 1
    return
  else:
    size //= 2
    recursive(row-size, col-size, size)
    recursive(row-size, col, size)
    recursive(row, col-size, size)
    recursive(row, col, size)

recursive(size-1, size-1, size)
print(data[r][c])

결과는

 

메모리 초과.

 

문제를 잘 보면 N = 15까지 갈 수 있다.

 

\(2^15\)...

 

너무나도 큰 값이기 때문에 당연히 메모리 초과가 발생할 수 있었다.

---

이후 백준의 질문 탭에 들어가서 메모리 초과를 어떻게 해결하는가에 대한 답변을 보고 싶어서 봤더니

 

위 문제는 배열로 풀지 않아도 되는 문제였다!

 

그래서 아래와 같이 풀었다.

import sys
input = sys.stdin.readline

n, r, c = map(int, input().split())
size = pow(2, n)

idx = 0
def recursive(row, col, size):
  global idx
  global r
  global c
  if size == 1:
    if r == row and c == col:
      print(idx)
      return
    idx += 1
    return
  else:
    size //= 2
    recursive(row-size, col-size, size)
    recursive(row-size, col, size)
    recursive(row, col-size, size)
    recursive(row, col, size)

recursive(size-1, size-1, size)

하지만 결과는

 

PyPy3으로 제출해도 시간 초과가 발생했다.

 

---

위 문제는 idx = 0부터 나눈 모든 것을 찾아가기 때문에 예를 들어서

 

10 1023 1023

 

이런 값이 입력되면

 

하루 종일 재귀를 하면서 1024 x 1024 배열을 모두 순환하여 값을 찾아낼 것이다.

 

당연히 시간 초과다.

 

그리하여 곰곰이 생각했다.

 

0	1
2	3

 

위의 사분면이 가장 클 때부터 작게 나눠질 때까지 계속해서 규칙성을 갖고 있기 때문에

 

넓은 범위부터 해당 값의 사분면이 위치한 방향으로 계속해서 좁히는 방법으로 값을 찾을 수 있다.

 

우선 n=2 일 땐

 

각 사분면의 맨 앞의 값은

 

0	1	4	5
2	3	6	7
8	9	12	13
10	11	14	15

0 4 8 12

 

n=3일 땐

0 16 32 48

 

그렇다면 n=4 일 땐?

 

0 64 128 256의 각 사분면의 맨 앞자리 숫자가 될 것이다.

 

위의 계산을 통해서 우리는 해당 값이 어디에 위치하는지 점점 좁히면서 찾을 수 있게 된다.

 

입력 예시중 하나인 3 7 7을 예시로 들면

 

row와 col 길이가 8인 8x8 배열에서 우리가 찾고자 하는 위치는 [7, 7] 위치이다.

 

각 사분면의 기준은 정 중앙이며

 

0 1

2 3

의 규칙으로 사분면을 나눌 때

 

0 사분면은 row < 4 && col < 4

1 사분면은 row < 4 && col ≥ 4

2 사분면은 row ≥ 4 && col < 4

3 사분면은 row ≥ 4 && col ≥ 4

 

위의 규칙으로 각 사분면을 나눌 수 있으며

 

각 사분면마다 맨 앞의 값은

 

0 16 32 48이었다.

 

이 값은 row * col * 사분면의 위치 값(0, 1, 2, 3) 

 

0 사분면 맨 앞의 값은 4 * 4 * 0 = 0

1 사분면 맨 앞의 값은 4 * 4 * 1 = 16

2 사분면 맨 앞의 값은 4 * 4 * 2 = 32

3 사분면 맨 앞의 값은 4 * 4 * 3 = 48

 

이를 코드로 나타내면

 

(Python 코드)

import sys
input = sys.stdin.readline

n, r, c = map(int, input().split())
idx = 0
while n != 0:
  n -= 1
  if r < 2**n and c < 2**n:
    idx += (2**n) * (2**n) * 0
  elif r < 2**n and c >= 2**n:
    idx += (2**n) * (2**n) * 1
    c -= 2**n
  elif r >= 2**n and c < 2**n:
    idx += (2**n) * (2**n) * 2
    r -= 2**n
  else:
    idx += (2**n) * (2**n) * 3
    r -= 2**n
    c -= 2**n
print(idx)

 

(Java 코드)

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

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException   {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String s = br.readLine();
		String [] s_arr = s.split(" ");
		int n = Integer.parseInt(s_arr[0]);
		int r = Integer.parseInt(s_arr[1]);
		int c = Integer.parseInt(s_arr[2]);
		int idx = 0;

		while(n != 0) {
			n--;
			double range = Math.pow(2, n);
			if(r < range && c < range) {
				idx += range * range * 0;
			} else if (r < range && c >= range) {
				idx += range * range * 1;
				c -= range;
			} else if (r >= range && c < range) {
				idx += range * range * 2;
				r -= range;
			} else {
				idx += range * range * 3;
				r -= range;
				c -= range;
			}
		}
		System.out.print(idx);
	}
}

---

 

 

Ref

 

https://ggasoon2.tistory.com/11

백준 1074번 - Z ( python )

 

 

Git 백준 1074번 - Z.py

Git 백준 1074번 - Z.java