[백준/Python] 1074번 : Z

문제 분석

https://www.acmicpc.net/problem/1074

재귀 탐색은 같은 패턴의 행동이 여러 번 반복될 때 쓰일 수 있다.

이 문제도 탐색 범위만 변경될 뿐 z모양으로 탐색하는 행동이 여러 번 반복되므로 재귀 탐색으로 풀 수 있다.

 

1. base condition(모든 입력값에 대해 귀결되는 조건)은 (r, c)에 도달하는 것
   이 부분이 재귀 탐색 안에 종료 조건으로 포함됨
2. 함수를 정의해보자. 한 변의 길이가 k인 정사각형을 z모양으로 탐색하면 된다.
   정사각형을 사등분해서 맨 왼쪽 위에 있는 좌표들을 재귀호출함

오답 노트

Z모양으로 탐색이 반복되므로 한 변의 길이가 K인 정사각형을 네 개로 분할한 후 탐색을 반복해야겠다고 생각함

그리고 r, c를 찾았음에도 불구하고 그 뒤의 좌표까지 다 세어지길래 재귀 탐색 맨 처음에 r, c를 찾으면 더 이상 탐색하지 않게 만듦

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

flag = False
totalcnt = 0
def search(a:int, b:int, k:int, cnt) -> None:
    global totalcnt
    global flag
    if flag:
        return
    if k==2:
        if a==r and b==c:
            totalcnt = totalcnt + cnt + 1
            flag = True
        elif a==r and b+1==c:
            totalcnt = totalcnt + cnt + 2
            flag = True
        elif a+1==r and b==c:
            totalcnt = totalcnt + cnt + 3
            flag = True
        elif a+1==r and b+1==c:
            totalcnt = totalcnt + cnt + 4
            flag = True
        else: # 찾지 못했을 때
            totalcnt = totalcnt + cnt + 4
        return

    search(a, b, k//2, cnt)
    search(a, b+k//2, k//2, cnt)
    search(a+k//2, b ,k//2, cnt)
    search(a+k//2, b+k//2, k//2, cnt)

search(0, 0, 2**n, 0)
print(totalcnt-1)

 

그러나 시간 초과가 발생 -> r, c가 속하지 않은 사분면은 탐색하지 않고 건너뛸 수 있다고 함

그러고 보니 그렇긴 하다. r, c를 알면.... 2^n*2^n의 범위를 좁힐 수 있다.

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

flag = False
totalcnt = 0
def search(a:int, b:int, k:int, cnt) -> None:
    global totalcnt
    global flag
    if flag:
        return
    # r, c가 현재 탐색 범위에 없으면
    if not(a<=r<a+k and b<=c<b+k):
        totalcnt += cnt + k*k
        return
    if k==2:
        if a==r and b==c:
            totalcnt += cnt + 1
            flag = True
        elif a==r and b+1==c:
            totalcnt += cnt + 2
            flag = True
        elif a+1==r and b==c:
            totalcnt += cnt + 3
            flag = True
        elif a+1==r and b+1==c:
            totalcnt += cnt + 4
            flag = True
        else: # 찾지 못했을 때
            totalcnt += cnt + 4
        return

    search(a, b, k//2, cnt)
    search(a, b+k//2, k//2, cnt)
    search(a+k//2, b ,k//2, cnt)
    search(a+k//2, b+k//2, k//2, cnt)

search(0, 0, 2**n, 0)
print(totalcnt-1)

(r, c)가 현재 탐색 범위에 없으면 현재 탐색 중인 범위에 포함된 좌표의 개수 k*k를 더해주는 로직을 추가했다.