[백준] 1074 - Z

1. 문제

1074번: Z

2. 개요

재귀 활용 문제.

Z자 탐색을 실행하고 이때 r행 c열을 몇 번째로 방문하는지 출력하면 된다.

3. 코드 및 추가내용

import sys

N, r, c = map(int, sys.stdin.readline().split())

board = [[0 for i in range(2**N)] for j in range(2**N)]

cnt = 0
def z_search(idx, a = 0, b = 0):
    global cnt
    if idx == 1:
        for i in range(a, a+2):
            for j in range(b, b+2):
                board[i][j] = cnt
                cnt += 1

    else:
        z_search(idx - 1, a, b)
        z_search(idx - 1, a, b + 2**(idx-1))
        z_search(idx - 1, a + 2**(idx-1), b)
        z_search(idx - 1, a + 2**(idx-1), b + 2**(idx-1))

z_search(N)
print(board[r][c])

처음엔 재귀를 이용하여 모든 칸을 방문하며 1씩 늘려준 후 해당 칸의 값을 출력해보았으나 시간초과로 실패했었다.

import sys

N, r, c = map(int, sys.stdin.readline().split())

cnt = 0
def z_search(idx, a = 0, b = 0):
    global cnt
    if idx == 1:
        if (a <= r <= a+1 and b <= c <= b+1) == False:
            cnt += 4
        else:
            cnt += (r-a) * 2 + (c-b)
            print(cnt)
            sys.exit()

    else:
        z_search(idx - 1, a, b)
        z_search(idx - 1, a, b + 2**(idx-1))
        z_search(idx - 1, a + 2**(idx-1), b)
        z_search(idx - 1, a + 2**(idx-1), b + 2**(idx-1))

z_search(N)

그래서 모든 칸을 방문하지는 않고 최소 규모인 4칸짜리일 때 목적 칸이 포함되는지를 판별하여 실행횟수를 조금 줄여봤으나 여전히 시간초과였다.

import sys

N, r, c = map(int, sys.stdin.readline().split())

cnt = 0
def z_search(idx, a = 0, b = 0):
    global cnt
    if idx == 1:
        cnt += (r-a) * 2 + (c-b)
        print(cnt)
        sys.exit()

    else:
        if r < a + 2**(idx-1) and c < b + 2**(idx-1):
            z_search(idx - 1, a, b)
        elif r < a + 2**(idx-1):
            cnt += (2**(idx))**2 // 4
            z_search(idx - 1, a, b + 2**(idx-1))
        elif c < b + 2**(idx-1):
            cnt += (2**(idx))**2 // 4 * 2
            z_search(idx - 1, a + 2**(idx-1), b)
        else:
            cnt += (2**(idx))**2 // 4 * 3
            z_search(idx - 1, a + 2**(idx-1), b + 2**(idx-1))

z_search(N)

위 방법을 더 넓게 사용해서 애초에 처음부터 목적 칸이 포함될 곳만 재귀로 탐색하는 방식을 사용해 봤더니 성공했다.