[DP] 12906 새로운 하노이 탑 python

📄 12906 새로운 하노이 탑 📄

www.acmicpc.net/problem/12906

12906번: 새로운 하노이 탑

---

🤔 문제 풀이  🤔

pypy3로 채점을 하면 메모리 초과 발생!

 

이 문제의 핵심은 어떻게 방문 체크를 할것인지를 파악하는 것이다.

 

기본적인 BFS처럼 배열로 방문체크를 할 수가 없다.

 

각각의 기둥에 들어가있는 원판을 "/"으로 구분시켜 하나의 문자열로 만든다.

이 후 set()나 dict()를 이용해 문자열의 중복 방문 여부를 확인해주면 된다.

---

⌨️ 코드 ⌨️

import collections

arr = [input()[2:] for _ in range(3)]
#visited = set()
visited = collections.defaultdict(int)
q = collections.deque()

q.append((arr[0], arr[1], arr[2], 0))

while q:
    a, b, c, count = q.popleft()
    cont_str = a + "/" + b + "/" + c

    if 'B' not in a and 'C' not in a:
        if 'A' not in b and 'C' not in b:
            if 'A' not in c and 'B' not in c:
                print(count)
                exit(0)

    #if not cont_str in visited:
        #visited.add(cont_str)
    if not visited[cont_str]:
        visited[cont_str] += 1

        if len(a) > 0:
            q.append((a[:-1], b + a[-1], c, count + 1))
            q.append((a[:-1], b, c + a[-1], count + 1))
        if len(b) > 0:
            q.append((a, b[:-1], c + b[-1], count + 1))
            q.append((a + b[-1], b[:-1], c, count + 1))
        if len(c) > 0:
            q.append((a, b + c[-1], c[:-1], count + 1))
            q.append((a + c[-1], b, c[:-1], count + 1))

print(-1)

---

Reference

•