[Python] 17370번 육각형 우리 속의 개미

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

17370번: 육각형 우리 속의 개미

---

 

23/09/25

 

 

육각형을 어떻게 적절하게 잘 변형시키는 가가 관건인 문제다.

---

 

문제 접근 방식:

 

 

문제를 처음 보고 규칙성이 있는 DP문제인 줄 알고 한참 동안 점화식을 찾아 해맸다.

 

이후 규칙성이 없음을 깨닫고 백트래킹으로 접근했다.

 

이 문제의 핵심은 육각형을 어떻게 적절하게 잘 변형 시킬 수 있는가 이다.

 

일반적인 2차원 격자로는 상하좌우로 움직이기 때문에 120도 만큼을 돌아가는 것을 어떻게 표현할 수 있는지를 알아야 이 문제의 구현이 쉬워질 것이다.

 

갔던 정보를 실수로 접근하여 구하는 방법도 존재하지만, 이는 실수 오차가 존재할 수 있기 때문에, 나는 육각형의 격자를 조금 길쭉하게 늘려, 다음과 같은 모양의 격자로 변형 시켰다.

 

 

이렇게 육각형을 120도를 돌리도록 하는 것이 아닌 90도와 135도를 돌리도록 구현하면 격자 위에서 DFS를 진행하는 것 처럼 구현할 수 있다.

 

처음에 그렇게 구현을 해서 제출을 했는데 시간초과가 났다.

 

제한이 $N=22$까지 였기 때문에, 로컬에서 돌리고 그 답을 제출하는 것으로 방향을 바꾸어서 맞았습니다를 받을 수 있었다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 17370번 육각형 우리 속의 개미
# DFS, 백트래킹
##import sys
##input = sys.stdin.readline
##vector = [(0, 2), (1, 1), (1, -1),
##          (0, -2), (-1, -1), (-1, 1)]
##
##N = int(input())
##total = 0
##def dfs(n, vector_num, visited, now_pos): # 몇개를 썼는가, 직전에 사용했던 벡터, 방문했던 좌표들, 현재 좌표
##    global total
##    if now_pos in visited:
##        if n == N:
##            total += 1
##        return
##    if n > N:
##        return
##    visited.append(now_pos)
##    new_pos1 = (now_pos[0]+vector[(vector_num+1)%6][0],now_pos[1]+vector[(vector_num+1)%6][1])
##    new_pos2 = (now_pos[0]+vector[(vector_num-1)%6][0],now_pos[1]+vector[(vector_num-1)%6][1])
##    dfs(n+1, (vector_num+1)%6, visited, new_pos1)
##    dfs(n+1, (vector_num-1)%6, visited, new_pos2)
##    visited.pop()
##    return
##
##dfs(0, 0, [(0, 0)], (0, 2))
##print(total)
N = int(input())
ans = [0, 0, 0, 0, 0, 2, 2, 4, 8, 26, 36, 80, 148, 332, 556, 1172,
       2112, 4350, 7732, 15568, 28204, 56100, 101640]
print(ans[N])