[백준] 1074번 Z (파이썬)

1074번: Z

문제

한수는 크기가 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

---

코드 

import sys

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

visit = 0
while n != 0:
    n -= 1
    size = 2 ** n

    # 1사분면
    if r < size and c < size:
        visit += 0

    # 2사분면
    elif r < size and c >= size:
        visit += size * size
        c -= size

    # 3사분면
    elif r >= size and c < size:
        visit += size * size * 2
        r -= size

    # 4사분면
    else:
        visit += size * size * 3
        r -= size
        c -= size

print(visit)

 

풀이 

• 배열을 4구역으로 나눠서 찾고자 하는 r행 c열의 좌표가 어느 구역에 있는지 찾아가면 된다.
  • 1사분면: 가로 < 2^(n-1) AND 세로 < 2^(n-1)
  • 2사분면: 가로 ≥ 2^(n-1) AND 세로 < 2^(n-1)
  • 3사분면: 가로 < 2^(n-1) AND 세로 ≥ 2^(n-1)
  • 4사분면: 가로 ≥ 2^(n-1) AND 세로 ≥ 2^(n-1)
• 아래 배열을 4분면으로 나누면, 시작점이 0, 4, 8, 12 이다.

 

• 이런 방법으로 visit에 더해서 몇 번째 칸까지 방문했는지를 더해준다.
• 이걸 반복하기