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

문제 풀이 날짜: 2023.05.20
포스트 작성일: 2023.05.21

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

백준 온라인 저지 1074번: Z (실버1)

 

키워드

분할 정복

 

풀이 접근법

• 입력이 2의 제곱수 꼴로 주어졌으므로 이분탐색을 이용한다.
• 주어진 배열의 크기는 2^N × 2^N이다. 만약 이것을 재귀적으로 풀고 싶다면 그 이전에 2^{N - 1} × 2^{N - 1} 크기 배열(4분의 1 사이즈)을 계산한다.
• 찾는 좌표가 몇 사분면에 있는 지를 기준으로 각기 다르게 재귀 호출을 해야 한다.
• 배열의 크기를 4분의 1로 나누어 Z모양으로 탐색하므로, 한 번의 메소드 호출에서 재귀 호출이 4회 일어난다.
• 범위를 제한하지 않고 재귀 호출을 하면 시간 초과가 발생하므로, 두 가지 처리를 해준다.

1. 재귀 호출의 범위를 설정해주어야 한다.

• 현재의 위치에 따라 호출할 방향이 결정된다. 배열을 4등분 하여, 찾고 싶은 위치가 몇 사분면에 있는지에 따라 현재 좌표를 해당 사분면으로 이동시킨다.
• 좌표를 계속 이동시키다가 배열을 더이상 쪼갤 수 없거나, 현재 위치가 목표 좌표와 같은 경우 함수를 리턴시키고 결과를 출력한다.

2. 현재 위치가 몇 번째 칸인지 별도로 계산해주어야 한다.

• 위에서 서술한 대로, 모든 칸을 하나하나 다 탐색하면서 개수를 구하면 시간 초과가 발생한다.
• 따라서, 목표 좌표가 있는 곳으로 현재 좌표를 이동시키면서, 그동안 거쳐온 칸의 수를 별도로 더해주어야 한다.
• 예를 들어서, 현재 좌표가 (0, 0)이고 1사분면에 있을 때, 이를 3사분면으로 옮겼다면 1사분면과 2사분면에 존재하는 모든 칸의 수를 더해주어야 목표 좌표까지 다다르는 데 존재하는 칸의 수를 구할 수 있다.

 

코드

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

public class Main {
	
	private static int R;
	private static int C;
	private static int SIZE;

	private static int count = 0;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

		int N = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		SIZE = (int) Math.pow(2, N); //한 변의 크기

		recursion(SIZE, R, C);
		
		System.out.println(count);
	}
	
	private static void recursion(int size, int r, int c) {		
		if(size == 1) {
			return;
		}

		int half = size / 2;
		if(r < half && c < half) { //1사분면: row와 col이 모두 key보다 크면 호출
			recursion(half, r, c);
		} else if(r < half && c >= half) { //2사분면: R보다 row가 크면 호출
			count += size * size / 4; //1사분면의 수 skip
			
			recursion(half, r, c - half);
		} else if(r >= half && c < half) { //3사분면: C보다 col이 크면 호출
			count += (size * size / 4) * 2; //2사분면의 수 skip
			
			recursion(half, r - half, c);
		} else { //4사분면: row와 col이 모두 key보다 작거나 같으면 호출
			count += (size * size / 4) * 3; //3사분면의 수 skip
			
			recursion(half, r - half, c - half);
		}
	}

}

---

재귀 호출의 방향을 설정하는 데 어려움을 겪어, 다른 블로그를 참고하여 풀었다. 이와 유사한 matrix 분할정복 문제도 모두 좌표를 밀어주면서 계산한다.

 

참고한 링크

https://mygumi.tistory.com/284
https://wiselog.tistory.com/133

 

git 링크

(git 링크 첨부)