[백준] 1074 Z (JAVA) 풀이

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

분할 정복, 재귀 함수를 사용한 문제이다.

---

우선, Z가 지나온 방향으로 분석을 해보고자 했고, 대략적인 패턴은 발견했지만 이를 어떻게 구현해야 할지 감이 잡히지 않았습니다. 가장 아래 걸어둔 링크를 통해 해당 문제 패턴을 파악하였습니다.

 

 

풀이 방법

1. 배열을 사분면으로 나누고, 입력 받은 r, c가 몇 번째 사분면에 속하는지 확인합니다.

2. 재귀를 호출할 때마다 현재 r,c의 위치에 따라 앞 사분면에서 몇 번 방문했는지 더 하는 변수 count를 선언 합니다.

3. find 메소드를 정의하고, 매개변수로 한 변의 사이즈 size와 타겟 위치 인덱스 r, c를 넘깁니다.

 3-1. r과 c가 1사분면에 속한다면, 아무 곳도 방문하지 않았기 때문에 count를 그대로 둡니다. 현재 size의 절반, 1사분면의 현재 위치 r,c를 넘겨줍니다.

 3-2. 2사분면에 속한다면, 앞에서 1사분면을 방문해야 하기 때문에 count에 (size*size)/4 를 더합니다. 현재 size의 절반, 2사분면의 r, c -size/2 를 넘겨줍니다.

 3-3. 3사분면에 속한다면, 앞에서 1,2사분면을 방문해야 하기 때문에 count에 (size*size/4) * 2 를 더합니다.  현재 size의 절반, 3사분면의 r -size/2  , c넘겨줍니다.

 3-4. 4사분면에 속한다면, 앞에서 1,2,3사분면을 방문해야 하기 때문에 count에 (size*size/4) * 3 를 더합니다.  현재 size의 절반, 3사분면의 현재 위치 r-size/2,c-size/2를 넘겨줍니다.

 3-5. 위를 반복하다가 size가 1이 되면 더이상 방문할 곳이 없으므로 재귀를 끝냅니다.

4. count를 출력합니다.

 

예제 입력 1에서 N은 2, r은 3, c는 1 입니다. 

한변의 길이는 2*2 이므로 size는 4이고, 현재 인덱스는 (3,1) 이며 3사분면에 속해있습니다. 1,2 사분면에 필수로 방문해야하기 때문에 (4 * 4 / 4) * 2 = 8 입니다. 여기서 11이 되기 위해서는 3의 위치(1,1)로 이동해야 합니다. 3사분면은 확인이 끝났기 때문에 절반으로 나누고, r - size/2 하면 1이 되어 1사분면으로 이동하게 됩니다.

예제 입력 1의 사분면 이동 방향

 

정답 코드

package Baekjoon.sliver;
import java.util.*;
import java.io.*;
/*
 * 1074 Z
문제 접근
- 배열을 사분면으로 나누고, 재귀함수로 count 계산

문제 풀이
- 주어진 것 : 한 변의 size, 타겟 위치 인덱스 r,c를 입력 받음
- 타켓 위치가 어느 사분면에 속하는지 확인하여 계산
-> 한 사분면의 크기를 전체 배열 크기의 4등분

생각해볼것
- 2,3,4사분면에 속하면 앞 사분면을 반드시 방문하는 count를 계산
-> 2사분면 : count += size * size / 4;
-> 3사분면 : count += (size * size / 4) * 2;
-> 4사분면 : count += (size * size / 4) * 3;
 */
public class bj1074 {
	static int size, r, c;
	static int count = 0;
	public static void main(String[] args) throws Exception {
		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); // 한 변의 길이
		find(size, r, c);
		System.out.print(count);
	}
	
	static void find(int size, int r, int c) {
		if(size == 1) return; // 더이상 확인해야할 size가 없으므로 해당 재귀 함수를 나간다.
		
		if(r < size/2 && c < size/2) { // 1사분면
			find(size/2, r, c);
		} else if(r < size/2 && c >= size/2) { // 2사분면
			count += size * size / 4; // 1사분면에 방문했던 횟수를 count에 추가한다. 
			find(size/2, r, c - size/2);
		} else if(r >= size/2 && c < size/2) { // 3사분면
			count += (size * size/4) * 2; // 1,2사분면에 방문했던 횟수를 count에 추가한다.
			find(size/2, r - size/2, c);
		} else { // 4사분면
			count += (size * size/4) * 3; // 1,2,3사분면에 방문했던 횟수를 count에 추가한다.
			find(size/2, r - size/2, c - size/2);
		}
		
	}
}

 

 

 

 

 

 

Reference

https://ggasoon2.tistory.com/11

백준 1074번 - Z ( python )