문제
https://www.acmicpc.net/problem/1074
1074번: Z
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을
www.acmicpc.net
풀이
분할 재귀 방식의 문제였다. 분할, 재귀가 필요하다는 것을 보자마자 알 수 있었지만 구현하는데 까지는 시간이 좀 걸렸다. 타 블로그를 활용하였다.
참고 블로그 : https://mygumi.tistory.com/284
백준 1074번 Z :: 마이구미
이 글은 백준 알고리즘 문제 1074번 "Z" 을 풀이한다. 풀이 방법으 말하자면, 분할 정복 알고리즘이다. 분할 정복이란, 문제를 작은 부분으로 쪼개어 해결하는 방식이다. 문제 링크 - https://www.acmic
mygumi.tistory.com
중요한 점은 코드내에서 y, x는 항상 해당하는 사분면의 가장 왼쪽 위라고 판단하여 시작한다.
또한 해당하는 사분면이 아니라고 판단시 size^2를 더해주고 다음 재귀를 타서 사분면을 이동시킨다.
또한, 주의해야할점은 원하는 좌표를 찾았을 때 바로 결괏값을 출력하고 리턴하여 끝내줘야 한다. 다시 main문으로 result를 끌고 오면 else문을 타고 돌아올 수 있어서 result값이 변경될 수 있다.
코드
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int N, R, C;
int result;
void Z(int y, int x, int size) { //y,x는 각각 사분면 시작 왼쪽위,왼쪽아래를 향함
if (y == R && x == C) {
cout << result;
return;
}
if (R < y+size && C < x+size && R >=y && C >= x) { // 사분면 내에 존재시
//분할재귀
Z(y, x, size / 2); // 1사분면
Z(y, x+size/2, size / 2); // 2사분면
Z(y+size/2, x, size / 2); // 3사분면
Z(y+size/2, x+size/2, size / 2); // 4사분면
}
else { //사분면 내 존재 안할시 다음사분면 이동
result += size * size;
}
}
int main() {
cin >> N >> R >> C;
Z(0, 0, (1 << N));
return 0;
}