[Python/Java] 백준 1074번: Z (Gold 5)

💻 Problem

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

N > 1인 경우, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

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

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

 

💡 Approach

1. 2차원 배열의 영역을 4분할한다.
   • Z 순서대로 왼쪽 위(0), 오른쪽 위(1), 왼쪽 아래(2), 오른쪽 아래(3)
2. 이동 횟수는 0으로 시작한다.
3. 4개의 영역 중 타겟 좌표가 어디에 위치하는지 찾는다.
4. 타겟 좌표가 위치하는 영역까지 이동한다.
   • N = 3, 타겟 좌표 (3, 1)인 경우
     • 0번째 영역이니 0번째 영역의 시작점인 0에 그대로 위치한다.
   • N = 3, 타겟 좌표 (3, 5)인 경우
     • 1번째 영역이니 1번째 영역의 시작점인 16까지 이동
5. 해당 영역에서 다시 4분할하여 3~4 반복(재귀)
   • 배열의 크기(가로, 세로 크기)가 절반이 됨
6. 배열의 크기가 1이 되면 타겟 좌표를 찾은 것이다.

 

✏️ Solution

📝 Python 풀이

import sys
input = sys.stdin.readline

def search_z(row, col, cur_size):
    global count

    # 기저 조건: size가 1일 때
    # 배열의 크기가 1 * 1이면 
    if cur_size == 1:
        return

    area_size = cur_size // 2 # 4분할 영역의 크기

    # 현재 좌표가 몇 번째 영역인지 찾는다
    # 해당 영역으로 이동 후에 재귀를 호출한다

    # 왼쪽 위(0)
    if row < area_size and col < area_size:
        search_z(row, col, area_size)

    # 오른쪽 위(1)
    elif row < area_size and col >= area_size:
        count += (cur_size ** 2) // 4 # 1/4
        search_z(row, col - area_size, area_size)

    # 왼쪽 아래(2)
    elif row >= area_size and col < area_size:
        count += (cur_size ** 2) // 4 * 2 # 2/4
        search_z(row - area_size, col, area_size)

    # 오른쪽 아래(3)
    elif row >= area_size and col >= area_size:
        count += (cur_size ** 2) // 4 * 3 # 3/4
        search_z(row - area_size, col - area_size, area_size)
    
N, r, c = map(int, input().split()) # (r, c): 타겟 좌표
size = 2 ** N # 배열의 크기 size * size
count = 0 # 몇 번째로 방문하는지 세는 변수(이동 횟수)
search_z(r, c, size)
print(count)

 

📝 Java 풀이

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

/**
 * 1. N(배열 크기의 지수에 해당하는 수), 타겟 탐색 위치를 입력받는다.
 *    1-1. 배열 크기는 2^N이다.
 * 2. 배열을 4등분해서 타겟 위치가 어디에 속하는지 탐색한다.
 * 3. Z 모양 순서로 0, 1, 2, 3칸 중에 0번째 칸이 아니라면 0번째 칸으로 이동한다.
 *    3-1. 이동한 횟수는 moveCount에 더한다.
 * 4. 타겟 위치가 속하는 부분 배열에서 2x2 배열이 될 때까지 2~3번을 반복한다.
 */
public class Main {
	public static BufferedReader br;
	public static StringTokenizer st;
	
	public static int exponent; // 지수
	public static int size; // 배열의 길이
	public static int targetRow, targetCol; // 타겟 탐색 위치
	public static int moveCount; // 이동 횟수
	
	public static void searchZ(int row, int col, int size) {
		// 2칸보다 작아지면 탐색을 더 진행하지 않는다
		if (size == 1) {
			return;
		}
		// 왼쪽 위 칸(0)
		if (row < size / 2 && col < size / 2) { 
			searchZ(row, col, size / 2);
		}
		// 오른쪽 위 칸(1)
		else if (row < size / 2 && col >= size / 2) {
			// 4등분 중 한 칸만큼 이동하니까 전체(size * size)의 1/4을 이동 횟수에 더한다
			moveCount += size * size / 4;
			// 왼쪽으로 이동해야 하므로 행은 그대로고 열만 왼쪽(-)으로 이동한다
			searchZ(row, col - size / 2, size / 2);
		}
		// 왼쪽 아래 칸(2)
		else if (row >= size / 2 && col < size / 2) {
			// Z 모양의 두 번째 칸이므로 size * size / 4에 2를 곱한다 
			moveCount += (size * size / 4) * 2;
			// 위로 이동해야 하므로 행은 위(-)로 이동하고 열은 그대로이다
			searchZ(row - size / 2, col, size / 2);
		}
		// 오른쪽 아래 칸(3)
		else if (row >= size / 2 && col >= size / 2) {
			// Z 모양의 두 번째 칸이므로 size * size / 4에 3를 곱한다 
			moveCount += (size * size / 4) * 3;
			// 왼쪽 위로 이동해야 하므로 행은 위(-)로 이동하고 열도 왼쪽(-)으로 이동한다
			searchZ(row - size / 2, col - size / 2, size / 2);
		}
	}
	
	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		
		st = new StringTokenizer(br.readLine().trim());
		exponent = Integer.parseInt(st.nextToken());
		targetRow = Integer.parseInt(st.nextToken());
		targetCol = Integer.parseInt(st.nextToken());
		
		size = (int) Math.pow(2, exponent);
		
		moveCount = 0;
		
		// 타겟 위치를 시작으로 탐색하여 2*2 크기의 왼쪽 위 칸 배열이 될 때까지 쪼갠다
		searchZ(targetRow, targetCol, size);
		
		System.out.println(moveCount);
	}
}

 

예전에는 자바로 풀이했어서 같이 올린다.