백준 1074: Z

문제 요약

BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오.

문제 분류

• 분할 정복
• 재귀

문제 풀이

문제를 푸는 여러 방법이 있겠으나, 간략하게 구현한 것 같아 올린다.
주요 아이디어는 사분면으로 나누었을 때, 각 포인트를 저장하는 것이 아니라 왼쪽 위의 포인트와 사분면의 한 변의 길이로 계산을 했다.
사분면은 왼쪽 위부터 Z순으로 순회하도록 dir[]][]을 설계했고, 계산을 통해 현 탐색중인 사분면의 왼쪽 위 좌표를 얻어냈다.

첫 호출 시 사각형의 크기도 1 << n의 시프트 연산으로 구했다.

풀이 코드

#include <stdio.h>	
#include <iostream>

using namespace std;

int res, n, r, c;
int dir[4][2] = { {0, 0}, {0, 1}, {1, 0}, {1, 1} };

void sol(int i, int j, int len) {
	int l = len / 2;
	for (int k = 0; k < 4; k++) {
		int curi = i + dir[k][0] * l;
		int curj = j + dir[k][1] * l;
		if (curi <= r && r < curi + l
			&& curj <= c && c < curj + l) {
			sol(curi, curj, l);
			break;
		}
		res += l * l;
	}
}

int main() {
	cin >> n >> r >> c;
	sol(0, 0, 1 << n);
	printf("%d", res);
	return 0;
}