[Python][백준 17370][DFS][미해결] 육각형 우리 속의 개미 - 컴도리돌이

반응형

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

---

해당 문제는 

정말 주어진대로 문제를 풀었습니다.

 

똑같은 곧을 방문한 적이 있으면 출력 값을 1 더해주고 반환해주고,

개미 놈이 이동할 수 있는 경우를 다 설정하여 해당 방향에서

양 갈래 길로 가는 경우로 dfs 탐색을 해주었습니다..

 

하지만 python으로는 이렇게 주어진 대로 문제를 해결하면 시간 초과가 발생하네요..

 

경우의 수가 1부터 22까지이기 때문에 미해결 코드로 1부터 22까지 출력해서 

밑에 코드로 제출했더니 통과가 되었네요..

 

print([0, 0, 0, 0, 2, 2, 4, 8, 26, 36, 80, 148, 332, 556, 1172, 2112, 4350, 7732, 15568, 28204, 56100, 101640][int(input())-1])

 

파이썬으로 통과하신 분

코드 길이를 보시면 다 위에 처럼 푸신 거 같습니다.

하지만 제 밑에 595B는 제대로 푸신 거 같은데

너무 궁금하네요 

😂

코린이 궁금합니다.

 

혹시 python으로 해결하신 분 

코드 공유해주시면 감사하겠습니다. 하하

---

미해결 코드.

dx,dy,dir = [-1,-1,1,1,1,-1],[0,1,1,0,-1,-1],{0 : [1,5],1 : [0,2], 2 : [1,3], 3 : [2,4],4 : [3,5], 5 : [0,4]}
graph = [[False] * 100 for _ in range(100)]; graph[51][50],answer = True,0
def dfs(x,y,depth,d,n) :
  global answer
  if depth == n :
    if graph[x][y] : answer += 1
    return
  if graph[x][y] : return
  graph[x][y] = True
  dfs(x + dx[dir[d][0]],y + dy[dir[d][0]],depth+1,dir[d][0],n)
  dfs(x + dx[dir[d][1]],y + dy[dir[d][1]],depth+1,dir[d][1],n)
  graph[x][y] = False
dfs(50,50,0,0,int(input()))
print(answer)