백준 1074번 - Z (파이썬)

폭풍같은 한 주가 지났지만, 여전히 우린 WEEK 01이다.
정글은 목요일을 기준으로 새로운 WEEK으로 넘어가기 때문이다.

일요일은 기필코 쉬겠단 마음으로 갈아넣은 결과, 토요일 저녁 먹고 나서 일단 정렬 4문제 말고는 다 풀기는 했다. 물론 모든 문제를 혼자의 힘으로 푼건 아니다. N-Queen은 도저히 모르겠어서 너튜브 영상을 찾아봤고, 하노이도 진짜 고민하면서 6-x-y란 개념을 생각해냈지만 마지막 단계에선 약간의 도움을 받았다. 그리고 외판원 문제도 풀긴 했는데, 처음에 재귀로 안 풀어서 다시 재귀로 하는 과정에서 애먹었고! 이렇게 세 문제는 오늘 내일 중으로 무조건 다시 공부할 것이다.

다행히 다른 문제는 모두 내 힘으로 풀었는데, 그 중 가장 뿌듯했던 Z문제에 대한 풀이를 개발일지로 남겨보고자 한다.

최종코드 미리보기

# Z 탐색

import sys
N, R, C = map(int, sys.stdin.readline().strip().split())

def explore_Z(n,r,c):
    if n==0:
        return 0
    else:
        half = 2**(n-1)
        adder = 2**(2*n-2)
        if r < half :
            if c < half :
                return adder * 0 + explore_Z(n-1, r, c)
            else:
                return adder * 1 + explore_Z(n-1, r, c-half)
        else:
            if c < half :
                return adder * 2 + explore_Z(n-1, r-half, c)
            else:
                return adder * 3 + explore_Z(n-1, r-half, c-half)

print(explore_Z(N,R,C))

Z가 어떤 문제인지는, 아래의 링크와 그림을 참고하면 될 것이다.

백준 1074번 Z문제 바로가기

우선 강의실에서 이 문제를 처음 봤을 때, 나 역시도 이 웅장한 비주얼에 압도당했다. 헛웃음이 절로 나오더라. 뭔 이런...... 시간이 그때 이미 금요일에서 토요일로 넘어가는 새벽 2시 경이었는데, 한 30분 동안 이리저리 짜보면서 해봤는데 자꾸 출력이 제대로 되지 않았다. 분명 전체적으로 큰 Z 를 그리는건 맞는데....?

결국 포기하고 그날은 자러 가고, 잠들면서도 이 문제가 해결될랑 말랑 했던거에 미련이 남았는지 자꾸 생각이 났다. 그렇게 머리가 지끈지끈한 느낌으로 잠들었고, 토요일 아침에 일어나서 바로 샤워를 하는데 갑자기 새로운 접근법이 생각났다. 가로로 한번 반으로 자르고, 세로로 또 한번 반으로 자르면, 뭔가 간단하게 풀 수 있을듯한 느낌이 났다.

그렇게 토요일 아침에 나와서, 10분 동안 좀 전에 샤워하면서 했던 생각을 아래와 같이 정리해보았다. 그리고, 코드로 옮겨 보았다. 참고로, 나는 제일 간단하게 N=1 (크기 4) 인 경우에서 N=0 (크기 1) 인 경우로 축소하는 것에서 아이디어를 얻었다.

0) 우선 재귀의 기본 조건을 설정해 보았다.
N = 0인 경우, 크기가 2 ⁰ x 2 ⁰ = 1인 배열이다.
데이터가 0행 0열 하나 뿐이니까 언제나 자기 자신을 0번째로 방문하겠지?

따라서 return 은 0 으로 설정해주었다.

def explore_Z(n,r,c):
    if n==0:
        return 0 

1) 결국 N이 몇이든 커다란 Z를 그리고 있다는 점은, 이렇게 볼 수 있다! 그리고 이 큰 Z에서 섹션 0 ~ 섹션 3 중에 어디에 속하는지 확인해보았다.

우선 가로로 절반을 자른다. 예를 들어 n=1인 경우, 2 ¹ x 2 ¹ = 4 크기의 배열이니까, 길이가 가로 = 세로 = 2¹ 이다. 그럼 절반인 half = 2 ¹⁻¹ = 2 ⁰ = 1이겠지? 따라서, n의 길이가 1 이상이면 half = 2 ⁿ⁻¹ 이 된다고 생각했다.

half = 2**(n-1)

잘라봤다. 위쪽(섹션 0 or 1)인지, 아래쪽(섹션 2 or 3)인지. row가 half 보다 작으면 반으로 갈랐을 때 위쪽이고, 아니라면 반으로 갈랐을 때 아래쪽이다.

if r < half :
	# 섹션 0 or 섹션 1
else:
	# 섹션 2 or 섹션 3

같은 방식으로, 왼쪽(섹션 0 or 2)인지, 오른쪽(섹션 1 or 3)인지 판단했다. column이 half보다 작으면 반으로 갈랐을 때 왼쪽이고, 아니라면 반으로 갈랐을 때 오른쪽이다.

if r < half :
	if c < half : # 섹션 0
	else: # 섹션 1
else:
	if c < half : # 섹션 2
    else: # 섹션 3
               

어떤 경우에든, 재귀를 통해 최종적으로는 섹션 0에 위치하도록 줄여줄 수 있지 않을까? 2² x 2² = 16 크기의 배열에서 동그라미 친 4개의 위치를 조정해, 모두 0행 0열로 만들어보니 아래와 같은 규칙을 따른다는 것을 발견했다.

# 섹션 0인 경우. 즉, r과 c가 모두 half보다 작은 경우.
explore_Z(n-1, r, c)

0행 0열 ---> 0행 0열.

# 섹션 1인 경우. 즉, c가 half보다 큰 경우.
explore_Z(n-1, r, c-half)

0행 2열 ---> 0행 0열.

# 섹션 2인 경우. 즉, r이 half보다 작은 경우.
explore_Z(n-1, r-half, c)

2행 0열 ---> 0행 0열.

# 섹션 3인 경우. 즉, r과 c가 모두 half보다 큰 경우.
explore_Z(n-1, r-half, c-half)

2행 2열 ---> 0행 0열.

이렇게 재귀를 넘기면서 r과 c를 조정해주면 모두 섹션 0으로 바꿔줄 수 있다.

3) 마지막으로, 위와 같이 모두 섹션 0으로 r,c를 조절해줄 때, 기존의 커다란 Z를 봤을 때 섹션 0이 아닌 이상 (즉, 섹션 1-3인 경우), 이미 최소 2 ⁿ⁻¹ x 섹션번호 만큼은 출력 순서가 밀린다는 점을 고려해야 한다.

예를 들어, 마지막인 섹션 3의 경우, 이미 섹션 0~ 섹션 2에 포함된 배열의 크기 4+4+4 = 12 만큼은, 출력 순서에서 밀리게 된다. 섹션 3의 출력 순서가 12,13,14,15가 된 이유기도 하다. 따라서, 이를 섹션 0으로 조절해줄 때, 이 밀린 출력 순서만큼은 보존을 해줘야한다. 이를 반영하기 위한 변수로 adder를 설정해주었다.

adder = 2**(2*n-2)

n이 주어질 때, 섹션 하나의 크기는 2의 n-1승 x 2의 n-1승이다.
예시에서 n=2 일 때, 섹션 하나의 크기는 2²⁻¹ x 2²⁻¹ = 2 x 2 = 4 이며,
이게 adder의 크기가 된다.

그리고, 현재 몇 번째 섹션이냐에 따라서 그때그때 이 adder의 크기가 달라지는 것이다.
가령 섹션 3인 경우, 앞에 섹션 0,1,2 이렇게 세개나 있으니까 adder가 3번 더해져야 한다. 같은 논리로, 섹션 2의 경우 adder가 2번 더해져야 한다.

half = 2**(n-1)
adder = 2**(2*n-2)
if r < half :
	if c < half : # 섹션 0   
		return adder * 0 + explore_Z(n-1, r, c)
	else: # 섹션 1
		return adder * 1 + explore_Z(n-1, r, c-half)
else:
	if c < half : # 섹션 2
		return adder * 2 + explore_Z(n-1, r-half, c)
    else: # 섹션 3
        return adder * 3 + explore_Z(n-1, r-half, c-half)

• adder : 출력 순서가 보존될 수 있도록 해당 섹션 수만큼 넘겨주기.
• half : r과 c를 적절히 조정해주기.

위의 두 가지 요소를 활용하면 재귀를 활용해 최종 출력 순서를 구할 수 있다.
다시 한 번, 최종 코드는 다음과 같다.

# Z 탐색

import sys
N, R, C = map(int, sys.stdin.readline().strip().split())

def explore_Z(n,r,c):
    if n==0:
        return 0
    else:
        half = 2**(n-1)
        adder = 2**(2*n-2)
        if r < half :
            if c < half :
                return adder * 0 + explore_Z(n-1, r, c)
            else:
                return adder * 1 + explore_Z(n-1, r, c-half)
        else:
            if c < half :
                return adder * 2 + explore_Z(n-1, r-half, c)
            else:
                return adder * 3 + explore_Z(n-1, r-half, c-half)

print(explore_Z(N,R,C))

끝 !