2학년 2학기 알고리즘 과제_6주차(백준_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열을 몇 번째로 방문했는지 출력한다.

 

 

📙문제 풀이 ( 내 생각 및 기타 )

 

왜 문제 이름이 Z인가 했더니 방문하는 모양이 Z로 보여서 그런거였다. 

이렇게도 보고 저렇게도 봤지만, 생각보다 문제가 간단하게 풀릴 느낌이 아니었다.

일단 재귀 관련된 문제라는 거 까지는 알겠는데, 알고리즘 공부할때도 재귀가 많이 어렵다고 느껴졌던 지라..

일단 찾아봤다.

 

접근 방법

 

분할정복과 재귀로 접근할 수 있다고한다.

분할 정복으로 접근해보자.

 

 

분할 정복 문제는 가장 쉬운 경우에 답을 구하고, 어려운 경우는 쉬운 경우로 분할해서 푸는 방식으로 접근할 수 있다.

 

문제의 저의 접근 방법은 다음과 같다.

N이 1인지 확인합니다. N이 1이라면 2 x r + c 를 반환하고 종료한다.

 

N이 2 이상이라면, 주어진 점이 사사분면 중에서 몇 사분면에 있는지 확인한다. 그리고 해당지점을 4분의 1조각한다.

 

 

 

만약 해당 점이 2^(n-1)보다 크다면 좌표를 업데이트(new_point 함수)한다.

 

def new_point(point, n):
    return point - 2 ** (n - 1)

 

해당 사분면까지의 거리를 더한다.

1/4 조각한 사분면의 거리는 2^(n-1) * 2^(n-1) 입니다. 그래서 각 사분면마다 Z 거리를 더한다.

1사분면이라면 2^(n-1) * 2^(n-1) 을 더하고,

2사분면이라면 0 * 2^(n-1) * 2^(n-1) = 0 을 더하고, (즉, 안 더 합니다)

 

3사분면이라면 2 * 2^(n-1) * 2^(n-1) 를 더하고

4사분면이라면 3 * 2^(n-1) * 2^(n-1) 를 더한다.

 

 

📙 코드 분석

import sys

input = sys.stdin.readline

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


def new_point(point, n):
    return point - 2 ** (n - 1)


def dnc(n, r, c):
    if n == 1:
        return 2 * r + c

    # 2사분면
    if r < 2 ** (n - 1) and c < 2 ** (n - 1):
        return dnc(n - 1, r, c)
    # 1사분면
    elif r < 2 ** (n - 1) and c >= 2 ** (n - 1):
        return 2 ** (2 * n - 2) + dnc(n - 1, r, new_point(c, n))
    # 3사분면
    elif r >= 2 ** (n - 1) and c < 2 ** (n - 1):
        return 2 ** (2 * n - 1) + dnc(n - 1, new_point(r, n), c)
    # 4사분면
    else:
        return 3 * 2 ** (2 * n - 2) + dnc(n - 1, new_point(r, n), new_point(c, n))


print(dnc(n, r, c))

 

 

• n: 격자의 크기가 2n×2n2^n \times 2^n2n×2n임을 나타냄.
• r: 찾고자 하는 셀의 행 번호(0부터 시작).
• c: 찾고자 하는 셀의 열 번호(0부터 시작).
• 주어진 좌표(point)가 현재 사분면 기준으로 어느 위치에 있는지 계산하기 위해 2n−12^{n-1}2n−1을 빼서 새로운 좌표를 반환한다.
• 기저 조건: n=1n = 1n=1인 경우 21×212^1 \times 2^121×21 크기(2x2)의 격자가 되며, 순서를 직접 계산합니다.
  • 순서는 2×r+c2 \times r + c2×r+c로 간단히 구할 수 있음.
• 재귀적으로 사분면을 탐색
• 격자의 크기가 더 큰 경우 (2n×2n2^n \times 2^n2n×2n), 네 개의 사분면으로 나눠서 해당 좌표가 속한 사분면을 찾아 처리한다.
• 좌표가 왼쪽 위에 속하면, 그대로 n−1n-1n−1 크기의 격자로 재귀 호출.
• 좌표가 오른쪽 위에 속하면
  • 현재 격자의 왼쪽 위(2사분면)의 크기 22n−22^{2n-2}22n−2만큼 오프셋을 더함.
  • 열 좌표를 새롭게 조정 후 재귀 호출.
• 좌표가 왼쪽 아래에 속하면
  • 현재 격자의 위쪽 두 사분면(1, 2사분면)의 크기 22n−12^{2n-1}22n−1만큼 오프셋을 더함.
  • 행 좌표를 새롭게 조정 후 재귀 호출.
• 좌표가 오른쪽 아래에 속하면
  • 현재 격자의 위쪽 세 사분면(1, 2, 3사분면)의 크기 3×22n−23 \times 2^{2n-2}3×22n−2만큼 오프셋을 더함.
  • 행과 열 좌표를 조정 후 재귀 호출.
• 재귀 호출의 결과는 입력된 좌표 (r, c)에 해당하는 Z-모양 순서 번호를 반환한다.

 

 

 

📙 느낀점

 

역시 생긴거보고 끄적여봤을때, 문제가 꽤 까다롭다고 느껴져서 접근조차 하기 힘들었는데, 풀이를 보고도 너무 복잡하고 쉽지않음을 느꼈고,, 어려운 문제가 맞았다.

그냥 열심히 풀고 공부하는 수밖에!!

 

[ 참고 자료 ]

[알고리즘] 백준 1074번 Z 파이썬 python

[알고리즘] 백준 1074번 Z 파이썬 python