[백준] 1074번 : Z (🥈실버 1) (Python)

문제 바로 가기

1074번: Z

 

---

풀이

• 사용 언어 : Python
• 풀이한 날짜 : 2024-01-11

 

import sys
sys.setrecursionlimit(100000)

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

grid_n = 2 ** n

high_bound = 0
low_bound = 0


def divide(grid_n, start_r, start_c, start_num):
    global high_bound, low_bound

    total_num = grid_n ** 2

    # 초기 조건
    if r == start_r and c == start_c:
        print(low_bound)
        exit(0)

    if r >= start_r and r < start_r + (grid_n // 2) and c >= start_c and c < start_c + (grid_n // 2):
        # 제 2사분면
        low_bound = start_num
        high_bound = start_num + (total_num // 4) - 1
        divide(grid_n // 2, start_r, start_c, low_bound)

    elif r >= start_r and r < start_r + (grid_n // 2) and c >= start_c + (grid_n // 2) and c < start_c + grid_n:
        # 제 1사분면
        low_bound = start_num + (total_num // 4)
        high_bound = start_num + (total_num // 2) - 1
        divide(grid_n // 2, start_r, start_c + grid_n // 2, low_bound)

    elif r >= start_r + (grid_n // 2) and r < start_r + grid_n and c >= start_c and c < start_c + (grid_n // 2):
        # 제 3사분면
        low_bound = start_num + (total_num // 2)
        high_bound = start_num + ((total_num // 4) * 3) - 1
        divide(grid_n // 2, start_r + grid_n // 2, start_c, low_bound)

    else:
        # 제 4사분면
        low_bound = start_num + ((total_num // 4) * 3)
        high_bound = start_num + total_num - 1
        divide(grid_n // 2, start_r + grid_n // 2,
               start_c + grid_n // 2, low_bound)


divide(grid_n, 0, 0, 0)

 

풀이 로직

• 분할 정복 알고리즘으로 문제를 해결하였다.
• 주어진 행, 열 정보를 바탕으로 해당 위치가 정사각형 틀의 몇 사분면에 위치하는지 파악한다.
• 그리고 해당 사분면을 하나의 큰 정사각형 틀로 보고 다시 행과 열 정보를 바탕으로 이 틀에서 몇 사분면인지 파악한다.
• 이런 방식으로 계속 사각형 틀을 분할해나가 행, 열 정보에 해당하는 사각형을 찾는다.
• 물론, 사각형을 찾아나가는 과정에서 방문 순서의 범위도 함께 좁혀나간다.

 

•  변수 정보
  • 주어진 사분면에서 '방문 순서' 범위의 상한선 = upper_bound
  • 주어진 사분면에서 '방문 순서' 범위의 하한선 = lower_bound
  • 현재 정사각형 틀의 '방문 순서' 시작값 = start_num
  • 현재 정사각형 틀의 가로, 세로 길이 = grid_n
  • 현재 정사각형 틀의 전체 크기 = total_num
  • 사분면의 첫 탐색 위치의 행, 열 정보 = start_r, start_c

 

문제 접근 과정 및 느낀점

• 처음엔 좌표의 위치와 방문 순서 간의 규칙성을 파악하여 문제를 해결하려 했다.
• 하지만 이 방식은 모든 배열 공간을 탐색하는 방식이라 시간 초과 에러가 발생하였다.
• 그래서 배열의 일부만을 탐색하는 분할 정복 방법으로 문제를 처음부터 다시 접근할 수 밖에 없었다.
• 푸는 데 4시간이나 걸린 문제였다.. (이게 왜 실버..?)