백준 1074번 Z

2021년 06월 04일

---

백트래킹 공부하기(1)

매번 알고리즘을 공부할 때 마다 미루고 미루던 백트래킹을 드디어 시작했다

괜히 막 이름부터 어려울 것 같고 실제로 어렵다고도 하고...

일단 재귀가 어려워서 재귀를 제대로 이해 못하면 백트래킹은 손댈 수 없었다

그래서 우선 재귀를 공부했다

여기저기 구글을 돌아다니며 설명들을 주워담은 결과

재귀를 이해하기에 가장 좋았던 내용은

대충

1에서 2가 되고 n에서 n+1이 되면 다 된다고 생각하고 코드를 짜라

는 내용의 말이었다

뭔가 이 말은 보고나니 그동안 엄두도 못냈던 Z 문제를 풀 수 있을 것 같았다

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

백준 1074번 Z

하지만 역시 쉽지 않았다

규칙을 찾아내기까지 한참 걸렸고 코드화하는 것도 죙일 걸렸다

그런데 열심히 만들어놓고 제출했더니 시간초과가 떴다

코드를 차근차근 살펴보며 생각을 해봤더니

오른쪽 아래 지점에 있는 숫자를 찾을 때는 나머지 부분들은 갈 필요가 없다

근데 내 코드를 그냥 무식하게 모든 좌표를 다 찾아가고 있었다

이점을 개선하면서 보니 2차원 리스트를 만들어 좌표마다 숫자를 기록하고 있었다

근데 코드를 보면서 생각을 해보니 기록조차 필요가 없다

바로 2차원 리스트 삭제. 물론 제대로 가고 있나 확인할 땐 좋았다

옛날부터 바라만 보던 문제를 해결해서 정말 기분이 좋았다

from sys import stdin

def func(num, x, y, n):
  if x==r and y==c:
    print(num)
    return
  elif n==0:
    return
  nx = 2**(n-1)
  ny = 2**(n-1)
  
  if r<x+nx and c<y+ny:
    func(num,x,y,n-1)
  elif r<x+nx and c>=y+ny:
    func(num+4**(n-1),x,y+ny,n-1)
  elif r>=x+nx and c<y+ny:
    func(num+2*(4**(n-1)),x+nx,y,n-1)
  elif r>=x+nx and c>=y+ny:
    func(num+3*(4**(n-1)),x+nx,y+ny,n-1)
  

n, r, c = list(map(int, stdin.readline().split()))

func(0, 0, 0, n)