백준 1074. Z

🅰 백준 1074. Z

1074번: Z

✏️ 문제 풀이

• 백준의 색종이, 쿼드트리랑 비슷한 문제이다.
• 시간제한이 0.5초이기 때문에 모든 케이스를 탐색할 수는 없다.
• 재귀를 이용하여 2차원배열을 4등분하고, r,c가 위치하고 있는 배열만 탐색하도록 구현하였다.
• 그리고 나눠진 배열의 시작점을 매개변수로 보내주어서 r,c를 몇번째로 방문했는지 체크해주었다.

✏️ 소스코드

package divideandconquer;

import java.util.Scanner;

public class Main_실버1_1074_Z {
	static int r, c;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int in = sc.nextInt();
		int N = (int) Math.pow(2, in);
		r = sc.nextInt();
		c = sc.nextInt();

		search(0, 0, N, 0);

	}

	private static void search(int x, int y, int N, int s) {
		if (r > x + N || r < x || c < y || c > y + N) {
			return;
		}
		if (N == 2) {
			Loop1: for (int i = x; i < x + N; i++) {
				for (int j = y; j < y + N; j++) {
					
					if (i == r && j == c) {
						System.out.println(s);
						break Loop1;
					}
					s++;
				}
			}
			return;
		}
		int n = N / 2;
		search(x, y, n, s);
		search(x, y + n, n, (s + (n * n)));
		search(x + n, y, n, (s + (n * n * 2)));
		search(x + n, y + n, n, (s + (n * n * 3)));

	}

}

 

✅ 후기

• 몇번 풀어본 유형이라 쉽게 감을 잡을 수 있었다. 몇번째로 방문했는지 체크하는 부분을 구현하는데 생각을 많이 했던 것 같다. 2차원배열로 나오는 재귀함수는 쉽게 생각할 수 있겠는데 다른 문제가 나오면 재귀로 어떻게 구현해야 하는지 생각하는게 어렵다,,,,,, 화이팅하쟈,,