[Gold V] Z - 1074

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

분류

분할 정복, 재귀

제출 일자

2025년 11월 8일 17:17:04

문제 설명

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

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

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

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

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

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

코드

// - 아이디어
// 문제의 규칙대로 board를 방문 횟수로 채운다.
// r,c 행열의 값을 출력한다.
// --------------------------------- 위의 방법으로는 시간초과
// 다시 생각해보자.
// z모양으로 진행하지만 완전탐색 과정을 생략하고 각 다음 단계의 시작숫자는 매번 제곱수로 알 수 있다.
// 행,열 값이 속하는 섹터만 집중적으로 들어가면 4분의 1씩 탐색을 줄일 수 있다. log4의N이 나올것으로 예상
// 
// - 시간
// 재귀 전체순회시 2^n*2^n 일때 n은 최대 15이니, 2^15*2^15 -> 10^8 -> 완전탐색 1억 - 시간초과
// 
// - 자료구조
//
#include <iostream>

int N;
int r, c;

struct Point
{
	int x;
	int y;
};
void dfs(int n, int val)
{
	int mul = n * n / 4;
	if (n == 1) {
		std::cout << val;
		return;
	}

	int half = n / 2;
	if (r < half && c < half) { // 1
		dfs(half, val);
	}
	else if (r < half && c >= half) { // 2
		c -= half;
		dfs(half, val + mul * 1);
	}
	else if (r >= half && c < half) { // 3
		r -= half;
		dfs(half, val + mul * 2);
	}
	else if (r >= half && c >= half) { // 4
		c -= half;
		r -= half;
		dfs(half, val + mul * 3);
	}
}
int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);

	std::cin >> N >> r >> c;
	dfs(1<<N, 0);

	return 0;
}

생각

시간복잡도를 생각해보고, 당연히 시간초과가 날거라 생각했지만, DFS 접근이 맞는지 검증ㅇ르 위해 최초시도에는 전체배열에 DFS로 접근하면서 완전탐색을 시도했다. 답은 예제의 답안대로 잘나오지만 당연히 시간초과가 발생하였다.

방문하는 사각형을 보면 결국 4가지 섹터를 같은 규칙으로 방문하게 된다.

(숫자 순서대로 진행)

또한, 섹터를 보다보면 규칙이 보인다. Z모양으로 진행하지만 사각형을 단위로 모두 순회하고 다음 사각형으로 가다보니, 꼭 순회하지 않아도 큰범위에서 각 사각형의 시작점에 해당하는 값을 알 수 있다.

val은 현재 전체 섹터의 칸 개수*/4가 될것이다. 여기서는 4*4 니깐 val=4로 계산해보면 각 위치의 값을 알 수 있다.

즉 문제를 효율적으로 풀기위해선 4가지 섹터 중 답이 존재하는(행,열이 속하는) 섹터를 선택하고 거기서 또 4가지 섹터 중 하나를 찾아들어가다 결국 사이즈가 1*1이 될때 탈출해주면 되겠다.

원리는 이렇고 찾아가는 구현은 다들 다를거같은데, 나는 r,c를 섹터를 선택하면서 해당섹터의 시작점을 0,0으로 볼수있게 r,c를 조정하면서 재귀를 호출해주었다.