[BOJ] 1074. Z

Z 실패분류

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	18141	7501	5362	41.272%

문제

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

만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.

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

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

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

입력

첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1 

2 3 1

예제 출력 1 

11

예제 입력 2 

3 7 7

예제 출력 2 

63

풀이

문제에도 나와있듯 재귀를 사용해 푸는 문제다. 굳이 재귀함수를 사용하지 않아도 반복문으로 풀 수 있지만 재귀를 연습하고 싶어서 그렇게 풀어봤다. 아이디어는 알겠는데 구현을 못하겠어서 너무 힘들었다. 

재귀 함수에 인자로 필요한 것은, 칸의 사이즈 그리고 왼쪽 위 칸의 인덱스 i,j 이다. 

사이즈가 1이 되었다는 것은 4사이즈의 칸으로 줄여서 Z 모양 탐색을 할 수 있게 되었다는 것이다.  i,j 에서부터 네개의 칸이 r,c 와 같은지 확인하면서 global 변수로 선언한 stage(단계 수 기록) 변수를 증가시킴으로써 정답을 찾아낼 수 있다.

칸 사이즈가 1이 아닌 경우, 사이즈를 1씩 줄이면서 재귀호출을 진행한다. 이 때 큰 사이즈의 네모가 4개 사분면으로 나뉘기 때문에, 칸의 사이즈를 -1 하면서 재귀 호출 하고 i,j 는 네개로 나눠진 사분면 크기만큼 i,j에 더해서 각 칸의 왼쪽 위 칸을 가리키도록 한다. 

코드

N, r, c = map(int, input().split()) stage = 0 def Z(n,i,j):     global stage     if n==1:         if r==i and c==j:             print(stage)             return         elif r==i and c==j+1:             print(stage+1)             return         elif r==i+1 and c==j:             print(stage+2)             return         elif r==i+1 and c==j+1:             print(stage+3)             return         stage+=4         return     nextt = (2**n)//2     Z(n-1,i,j)     Z(n-1,i,j+nextt)     Z(n-1,i+nextt,j)     Z(n-1,i+nextt,j+nextt) Z(N,0,0)

cs