[Python] 1074. Z - 재귀적 사고와 분할정복

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

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

1074번: Z

---

2. 핵심 아이디어

 

이 문제의 핵심의 재귀적 사고를 하는 것이다. 

먼저 길이가 2인 정사각형에서 Z의 흐름을 보자

 

 

도착까지 걸리는 시간이 T라면

0번째인 칸까지 걸리는 시간은 0일것이다.

1번째인 칸까지 걸리는 시간은 1

2번째인 칸까지 걸리는 시간은 2

3번째인 칸까지 걸리는 시간은 3이 된다.

 

그런데 문제는 이것이 매우 많아지고 반복되면서

우리가 재귀적인 규칙을 발견하기 힘들게 한다.

 

 

 

그럼 다시 처음으로 돌아가서 길이가 2인 정사각형을

길이가 n이라고 생각해보자

 

그리고 각 영역의 첫칸의 방문순서를 한번 따져보자면

0'의 방문순서는 역시 0번째가 될 것이다.

 

1'의 방문순서는 0번째 구역에 있는 칸을

모두 돌고난 후에 방문하게 될것이다.

 

따라서 방문 순서는 전체 n*n 넓이의 1/4만큼 , 

즉, 0번째 구역의 칸의 개수인 n*n *(1/4) 를 돌고난 후가 될 것이다.

 

2'의 방문순서도 마찬가지다.

0과 1번 구역을 모두 돌고난 후인

n*n (*1/2)를 돌고난 후가 2'의 방문순서가 된다.

 

3'의 방문순서는 마찬가지로

0,1,2,를 모두 돌고난 후인

n*n* (3/4)번째가 될 것이다.

 

 

그럼 이제 우리는 매우 큰 사각형도

4개의 구역으로 나누어 생각할 수있다.

 

즉 0번째 구역에 있다면 순서에서 아무것도 더해주지 말고

1번째 구역에 있다면 지금 사각형 넓이의 1/4만큼을 더해주고

2번재 구역에 있다면 지금 사각형 넓이의 2/4만큼을 더해주고

3번째 구역에 있다면 지금 사각형 넓이의 3/4만큼을 더해주면 된다.

 

이걸 사각형의 넓이가 4일때까지 반복해주면 된다.

 

예를 들어서 우리가 25번째 방문하는 다음 사각형을 찾아간다고 생각해보자

답은 0으로 초기화되어 있는 result에 담아주겠다.

 

 

먼저 변의 길이가 8인 사각형을 기준으로 보았을 때

25는 1번째 구역에 있다.

 

따라서 전체 사각형 넓이인 64의 1/4인 16을 더해준다.

result+=16

 

다음으로 사각형의 넓이를 1/4로 줄여 다시보자

이번엔 변의 길이가 4인 사각형이다

 

25는 이중 2번째 공간에 있다.

따라서 전체 사각형 넓이인 16의 2/4만큼을 더해준다.

 

result=16 + 8

 

 

다음으로 사각형의 넓이를 1/4로 줄여 다시보자

이번엔 변의 길이가 2인 사각형이다.

 

25는 이중 1번째 공간에 있다.

따라서 전체 사각형 넓이인 4의 1/4만큼을 더해준다.

 

result = 16 + 8 +1

 

이렇게 방문순서인 25가 나오게 된다.

 

 

즉, 재귀적으로 현재 좌표가 어느 공간에 속하는지 확인하면서

방문 순서를 예측해주면 되는 문제였다.

 

그럼 이것을 코드로 구현해보자

 

 

---

3. 코드

result=0

def cnt(x,y, n):
  global result #결과를 전역변수에 담기 위해서

  if n==2: #반환 값 => 전체 사각형 넓이가 4일때
    if((x,y)==(0,0)): # => 0번째 공간
      result+=0
    elif (x,y)==(0,1): # => 1번째 공간
      result+=1
    elif (x,y)==(1,0): # => 2번째 공간
      result+=2
    elif(x,y)==(1,1): # => 3번째 공간
      result+=3
    return 
  
  #만약 변의 길이가 2보다 크다면
  if(x>=n//2 and y>=n//2): # 3번째 공간
    result+=int(n*n*3/4)
    return cnt(x-n//2, y-n//2, n//2) #=> 변의 길이를 줄여서 반환해줌
    
  elif(x>=n//2 and y<n//2): # 2번째 공간
    result+=int(n*n/2)
    return cnt(x-n//2, y, n//2)
    
  elif(x<n//2 and y>=n//2): #1번째 공간
    result+=int(n*n/4)
    return cnt(x,y-n//2,n//2)
    
  else: #0번째 공간
    return cnt(x,y,n//2)
  

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

cnt(r,c, 2**n)

print(result)

---

4.배운 점

phase 4에 접어들면서 분할정복과 재귀구현 파트가 종종 보이는 것 같다.

중요한 건 어떻게 규칙을 찾을지 큰 문제를 보고 고민하기보다

간단하고 기본적인 문제를 시작으로 귀납적으로 어떻게 공통규칙을 발견할 것인지 고민하는 자세인 것 같다.

 

예전에는 조금 어려워서 건너뛴 문제같은데 그래도 코드피지컬이 조금은 올라왔음을 느낀다.

 

>>비슷한 문제

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

2630번: 색종이 만들기