1074. Z

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초 (추가 시간 없음)	512 MB	97649	41794	31236	42.720%

문제

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

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

다음 예는 22 × 22 크기의 배열을 방문한 순서이다.

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

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

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2N

풀이

실패: 시간 초과

def Z(n, r, c):  
    global cnt  
    if r == R and c == C:  
        print(cnt)  
        exit()  
    if n == 0:  
        cnt += 1  
        return  
  
    i = 2**(n-1)  
    Z(n-1, r, c)  
    Z(n-1, r, c+i)  
    Z(n-1, r+i, c)  
    Z(n-1, r+i, c+i)  
    return  
  
N, R, C = map(int, input().split())     # 2의 N승  
cnt = 0  
Z(N, 0, 0)

• Z(n, r, c)의 역할: 위치 (r,c)에 도달할 때까지, 주어진 정사각형을 4칸으로 쪼개며 Z모양으로 방문함.
  • 전역변수
    • cnt: 이동 횟수
  • 매개 변수
    • n: 정사각형 한 변의 길이가 2^n일 때 이 n의 값
    • r, c: 목적지 좌표
  • 내부 동작
    • 만일 좌표에 도달했으면(if r == R and c == C: ), 지금까지 누적된 이동 횟수(cnt)를 출력하고 프로그램 종료(exit() )
    • 만일 영역이 다 쪼개져서 1칸 (1x1)에 도달하면, 그 위치로 이동한 것이기 때문에, cnt += 1을 하고 return
    • 다 아니라면, 영역을 4분의 1로 쪼개서 다시 Z함수 호출
      • 각 변 길이 2^n의 n값은 1이 줄어들어야함 (ex. 4였던 것이 2가 되어야함.)
      • 호출 순서는 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순이다.

시간 초과 해결 아이디어 1 → 실패

• n == 0까지 가는 게 아니라, n == 1로 뭉뚱그리고 그 중에서 r,c의 위치를 체크(checkRC(r,c))해서 값을 더해주는 방법으로 하면 어떨까?

def Z(n, r, c):  
    global cnt  
    if n == 1:  
        if R-1<=r<=R and C-1<=c<=C:  
            print(cnt + checkRC(r,c))  
            exit()  
        else: cnt += 4  
        return  
  
    i = 2**(n-1)  
    Z(n-1, r, c)  
    Z(n-1, r, c+i)  
    Z(n-1, r+i, c)  
    Z(n-1, r+i, c+i)  
    return  
  
def checkRC(r, c):  
    if r == R and c == C:  
        return 0  
    elif r == R and c == C+1:  
        return 1  
    elif r == R+1 and c == C:  
        return 2  
    else:  
        return 3  
  
  
N, R, C = map(int, input().split())     # 2의 N승  
cnt = 0  
Z(N, 0, 0)

성공

def Z(n, r, c):  
    global cnt  
  
    if r == R and c == C:  
        print(cnt)  
        exit()  
    i = 2 ** (n-1)  
    haveRC(n-1, r, c)           # 1사분면  
    haveRC(n-1, r, c+i)         # 2사분면  
    haveRC(n-1, r+i, c)         # 3사분면  
    haveRC(n-1, r+i, c+i)       # 4사분면  
    return  
  
def haveRC(n, r, c):            # 해당 범위에 target이 있는지 없는지  
    global cnt  
    i = 2**n  
  
    if (r <= R < r+i) and (c <= C < c+i):   # 있으면 탐색  
        Z(n, r, c)  
    else: cnt += (i*i)          # 없으면 해당 범위 넓이 만큼 더함  
  
N, R, C = map(int, input().split())  
cnt = 0  
Z(N, 0, 0)

• Z(n, r, c)의 역할: 위치 (r,c)에 도달할 때까지, 주어진 정사각형을 4칸으로 쪼개며 Z모양으로 방문함. → +) 직접 방문하는 게 아니라 이동 횟수만 카운트해서 더하는 방식으로 수정
  • (r, c)가 속하지 않은 영역의 경우 이동 횟수만 카운트
  • (r, c)가 속한 영역의 경우 원래처럼 탐색하기.

Computer #PS