백준 1074번: Z (C++)

문제 링크

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

1074번: Z

 

재귀라는 아이디어는 쉽게 얻을 수 있었다.

 

구체적인 구현을 하는 데에는 시간이 꽤 걸렸다.

 

문제 제목처럼, 2차원 배열 모양의 평면을 반복적인 Z 모양으로 탐색하는 것이다.

 

재귀 함수를 구현할 때, base condition(탈출 조건)을 2*2 즉 한 변의 길이가 2일 때로 설정하면 된다.

 

그리고 순회하면서 0부터 쭉 순회 순서를 카운트 해줘야하기 때문에 전역 변수로 cnt를 두었다.

 

그림을 보면 n = 2일 때는 n = 1일 때의 상황이 네 번 반복된다.

 

또한 n = 3일 때는, n = 2일 때의 상황이 네 번 반복된다는 것을 알 수 있다.

 

따라서 base condition이 아닌 n을 처리하기 위해서는 4번의 n - 1을 처리하는 과정이 필요하다는 것을 알 수 있다.

 

2의 n승 형태로 인자가 들어가기 때문에 1<<n을 사용했다.

 

#include<iostream>
using namespace std;
int cnt = 0;
int n, r, c;
void func(int len, int row, int col) {
	//base condition: n = 2일 때
	if (len == 2) {
		if (row == r && col == c) {
			cout << cnt << '\n';
			return;
		}
		else
			cnt++;

		if (row == r && col + 1 == c)
		{
			cout << cnt << '\n';
			return;
		}
		else
			cnt++;

		if (row + 1 == r && col == c)
		{
			cout << cnt << '\n';
			return;
		}
		else
			cnt++;

		if (row + 1== r && col + 1 == c)
		{
			cout << cnt << '\n';
			return;
		}
		else
			cnt++;

		return;
		
	}
	func(len / 2, row, col);
	func(len / 2, row, col + len / 2);
	func(len / 2, row + len / 2, col);
	func(len / 2, row + len / 2, col + len / 2);

}
int main(void) {

	
	cin >> n >> r >> c;
	func(1 << n, 0, 0);

	return 0;
}