[BOJ/PYTHON] 1074. Z

백준 문제 링크: https://www.acmicpc.net/problem/1074

문제 요약

배열을 Z모양(왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로)으로 탐색할 때, r행 c열을 몇 번째로 방문했는지

핵심 아이디어

재귀를 쓰면 되는데, 큰 거부터 구획으로 돌고 작은 거로 재귀로 넘어와야 한다.

이때 탐색 횟수를 더해주는 식으로 모든 칸을 일일이 다 재귀를 돌면 메모리 초과가 나온다. 사분면을 나눠 몇 사분면인지 체크 후 해당 사분면으로 들어가서 다시 나누면 된다.

풀이

# silver1-1074. Z

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, r, c = map(int, input().split())
visit_count = 0 # 방문 횟수

def visit_graph(y, x, num): # num: 제곱 적용된 배열 칸 개수. 
    global visit_count
    next_num = (num // 2) ** 2 
    if num == 1: return visit_count

    if x < num // 2 and y < num // 2: 
        return visit_graph(y, x, num // 2)
    if x >= num // 2 and y < num // 2: 
        visit_count += next_num
        return visit_graph(y, x - num // 2, num // 2)
    if x < num // 2 and y >= num // 2: 
        visit_count += next_num * 2
        return visit_graph(y - num // 2, x, num // 2)
    if x >= num // 2 and y >= num // 2: 
        visit_count += next_num * 3
        return visit_graph(y - num // 2, x - num // 2, num // 2)

print(visit_graph(r, c, 2**n))

Trouble Shooting

메모리 초과 코드

# silver1-1074. Z

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, r, c = map(int, input().split())
array = [[0] * 2**n for _ in range(2**n)]
visit_count = 0 # 방문 횟수

# 큰 거부터 구획으로 돌고 작은 거로 재귀로 넘어와야 함

def visit_graph(y, x, num): # num: 제곱 적용된 배열 칸 개수. 
    global visit_count
    next_num = num // 2
    if num == 2: 
        array[y][x] = visit_count + 0
        array[y][x + 1] = visit_count + 1
        array[y + 1][x] = visit_count + 2
        array[y + 1][x + 1] = visit_count + 3
        visit_count += 4
        return 
    visit_graph(y, x, next_num)
    visit_graph(y, x + next_num, next_num)
    visit_graph(y + next_num, x, next_num)
    visit_graph(y + next_num, x + next_num, next_num)

visit_graph(0, 0, 2**n)
print(array[r][c])

실행 시간

메모리 31256KB, 시간 44ms (python3)