[백준/파이썬] 1074번 Z 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1074번 Z
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

크기 2^N x 2^N 배열을 Z 순서로 방문할 때 좌표 (r, c)가 몇 번째로 방문되는지 구하는 문제입니다.

코드

N, r, c = map(int, input().split())

cnt = 0
flag = False
def search(x, y, size):
    global cnt, flag
    if size == 1:
        if (x, y) == (r, c):
            print(cnt)
            flag = True
        cnt += 1
        return
    if flag:
        return
    
    if r <= x+(size//2) and c <= y+(size//2):
        search(x, y, size//2)
    else:
        cnt += (size//2)**2
        
    if r <= x+(size//2) and c <= y+size:
        search(x, y+size//2, size//2)
    else:
        cnt += (size//2)**2
        
    if r <= x+size and c <= y+(size//2):
        search(x+size//2, y, size//2)
    else:
        cnt += (size//2)**2
        
    search(x+size//2, y+size//2, size//2)
        
search(0, 0, 2**N)

설명

현재 정사각형을 4분할해서 Z 순서(좌상, 우상, 좌하, 우하)로 탐색합니다.

목표 좌표가 포함되지 않은 사분면은 그 사분면의 칸 수((size/2)^2)만큼 cnt를 한 번에 건너뜁니다.

목표가 있는 사분면만 재귀로 내려가므로 효율적으로 순서를 구할 수 있습니다.

---

• 백준 문제풀이 전체 목록 보기

---