백준 | 1074 - Z (python)

💤 Z

분할 정복 (Divide and Conquer) 문제

 

 

---

✏️ 문제

한수는 크기가 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열을 몇 번째로 방문했는지 출력한다.

 

 

---

💡 해결방법

분할 정복 알고리즘 문제이다. 이 문제는 말 그대로 각각 분할한 후 합하는 경우로 생각하면 된다.

이 문제는 재귀함수를 사용해서 문제를 해결했다. 조금 복잡하긴 하지만 차근차근 반례를 비교하면서 고쳐야 할 점을 하나씩 고쳤다.

 

n=2 인 배열

예를 들어 n=2인 배열이 위와 같을 때 별표시가 되어있는 곳을 구해야 한다고 치자. 별 표시가 있는 곳에서 쓸 수 있는 최소한의 Z인 사각형을 제외하고는 모두 계산한 값을 한꺼번에 구하는 것이다. 즉 빨간색으로 칠해져 있는 곳을 각각 세면서 구하는 것이 아니라, 전체 범위의 3/4를 더한 후 가장 오른쪽 아래 남은 사각형 4개로만 계산을 하는 것이다.

 

1. 전체 배열을 4등분 하기

2. r,c가 속해있는 사각형을 제외하고 구할 수 있는 값을 모두 더하기 (이 과정을 재귀로 반복)

3. 가장 최소의 사각형에서 r,c 값을 더하기

 

이해가 잘 안될 수 있는데... n=3인 경우를 살펴보자.

 

사각형을 4등분 했을 때 별표시(r,c)를 구하기 위해 전체 배열의 1/2값을 한꺼번에 더하고

 

이번에는 큰 파란색 테두리가 있는 사각형만 고려한다. 재귀함수 호출을 통해 이전 사각형의 1/4 사각형에서 별표가 있는 최소의 사각형을 제외하고 이전 사각형 값을 더한다. 즉 파란색 빗금이 쳐져있는 사각형을 더한다.

이후 별표시(r,c) 값을 더해주면 된다.

 

과정을 이헣게 사각형이 줄어들 때 마다 각각의 1/4만큼 사각형이 0,0부터 다시 시작한다고 생각을 하면 편하다. 기존 n=3 사각형에서는 가장 첫번째 칸이 0,0 이었지만, 한번의 재귀함수 호출을 통해 별표시까지 이동을 하려면 왼쪽 아래 큰 파란색 테두리의 사각형 첫번째 칸이 0,0 되는 것이다.

 

설명하기도 복잡한 문제••• 머쓱

짱친이 도와줘서 겨우 풀었다,,

 

 

👩🏻‍💻 소스코드

# 1074 : Z

import sys
n, r, c = map(int, sys.stdin.readline().split())
# 증가하면서 구할 값 선언
cnt = 0


def dq(n, r, c, cnt):
    # 배열의 길이
    len = 2**n
    # 배열의 길이 / 2
    half_len = len//2
    
    # 배열의 길이가 2라면(2**1)
    if n == 1:
        # 왼쪽 위
        if r == 0 and c == 0:
            cnt += 0
        # 오른쪽 위
        elif r == 0 and c == 1:
            cnt += 1
        # 왼쪽 아래
        elif r == 1 and c == 0:
            cnt += 2
        # 오른쪽 아래
        elif r == 1 and c == 1:
            cnt += 3
        return cnt
    
    # 배열의 길이가 2가 아니라면 (재귀)
    else:
        # 만약 배열을 4등분 했을 때 r,c가 왼쪽 위에 속한다면 왼쪽 위 배열만 활용
        if r < half_len and c < half_len:
            return dq(n-1, r, c, cnt)

        # 만약 배열을 4등분 했을 때 r,c가 오른쪽 아래 속한다면 cnt는 전체중의 3/4 값을 더함
        if r >= half_len and c >= half_len:
            cnt += (len**2)//4 * 3
        # 만약 배열을 4등분 했을 때 r,c가 왼쪽 아래 속한다면 cnt는 전체의 1/2 값을 더함
        elif r >= half_len and c < half_len:
            cnt += (len**2)//2
        # 만약 배열을 4등분 했을 때 r,c가 오른쪽 위에 속한다면 cnt는 전체의 1/4 값을 더함
        elif r < half_len and c >= half_len:
            cnt += (len**2)//4
        # 다음 재귀를 위한 r,c 값 조정. 배열을 4등분 했을 때 r,c 값을 1/4 범위로 조정함
        if r-(2**(n-1)) >= 0:
            r = r-(2**(n-1))
        if c-(2**(n-1)) >= 0:
            c = c-(2**(n-1))
        # 재귀함수 호출
        return dq(n-1, r, c, cnt)


print(dq(n, r, c, cnt))

---