[백준/python] 1074번 Z

1. 문제

 

이 문제는 배열을 한 변의 길이가 2 ** n인 배열을 Z 모양으로 탐색하며

r행 c열을 몇 번째로 방문하는지 출력하는 프로그램이다.

r과 c, 그리고 순서 모두 0부터 시작한다.

 

2. 풀이

<아이디어>
재귀적으로 접근하기! 4등분을 반복한다!

<풀이>
1. 만약 size가 1이 될 경우 ans는 start로 초기화한다.
2. size가 2 이상인 경우 배열을 4등분하여 r과 c가 어디에 위치하는지 확인한다.
3. 해당 사분면에 대해서 r과 c의 값을 갱신하고 해당 조각의 가장 왼쪽 위가 몇 번째인지를 구한다.
4. 위와 같은 방법으로 find 함수를 반복한 뒤 ans를 출력한다.

 

3. 코드

import sys
input = sys.stdin.readline

def find(start, size, r, c):
    global ans
    if size == 1:
        ans = start
        return
    
    half = size // 2
    
    if r < half and c < half:
        find(start, half, r, c)
    elif r < half and c >= half:
        find(start + half * half, half, r, c - half)
    elif r >= half and c < half:
        find(start + 2 * half * half, half, r - half, c)
    else:
        find(start + 3 * half * half, half, r - half, c - half)

n, r, c = map(int, input().split())
ans = 0
find(0, 2 ** n, r, c)
print(ans)

 

4. 느낀 점

처음에 이 문제를 풀 때 r과 c 값을 바꾸는 대신 r과 c 각각의 half 위치를 바꾸는 형태로 접근했다.

그러나 이렇게 할 경우 너무 코드가 복잡해져 가독성이 떨어졌다.

이에 다른 아이디어를 생각하다가 r과 c에 변화를 주었는지 훨씬 코드가 간결해졌다.