백준) 1074번 Z

문제

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

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

입력 & 출력

• 입력
  : 첫째 줄에 정수 N, r, c가 주어진다.
• 출력
  : r행 c열을 몇 번째로 방문했는지 출력한다.

풀이

풀이에 앞서 다음 블로그의 내용을 참고하였습니다. https://ggasoon2.tistory.com/11

그림을 통해 이해 하자면

각 자리값 r,c를 두배를 하게되면 값은 4배가 상승합니다.
이를 활용하게되면 각 자리의 값은 전 값의 4배라는 규칙을 만들 수 있게됩니다.
따라서 다음과 같은 코드가 가능합니다.

def z(N,r,c):
	if N ==0:
    	return 0
	return 4 * z(N - 1, int(r / 2), int(c / 2))

그러나 가장 작은 Z의 값이 반영되지 않습니다. 따라서 가장 작은 Z에서의 r,c위치를 더해주면 코드가 완성됩니다.

def z(N, r, c):
    if N == 0:
        return 0
    return 2 * (r % 2) + (c % 2) + 4 * z(N - 1, int(r / 2), int(c / 2))

느낀점

: 아이디어를 잡아서 코드 풀이를 진행했었으나, 가장작은 Z를 처리하는 부분에서 막혔던 것 같다. 또한 아직 재귀 함수의 활용이 미숙해서 아쉬웠다.

참고

백준 1074번 - Z ( python ) : https://ggasoon2.tistory.com/11