[백준 - Python] 12906 - 새로운 하노이 탑

0. 문제 링크

 

 

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

12906번: 새로운 하노이 탑

---

1. 풀이 방법

 

 

이 문제의 관건은 어떻게 방문 처리를 할 것이냐 인듯하다..

편의상 1번, 2번, 3번 스택이라고 얘기하겠다.

나는 처음에 1번, 2번, 3번 따로 생각해서 중복 처리를 했는데, 이러면 문제가 생긴다.

따라서 1번, 2번, 3번을 합쳐서 방문 처리를 해야 한다.

예를 들면 1번에 A, 2번에 BC, 3번에 A 가 있으면 A.BC.A를 방문했다고 처리하는 것이다.

 

방문 표시를 str으로 변환하고, set에 넣어서 확인했다.  
그 뒤에는 하나하나 빼고, 넣은 다음에 큐에 넣었다.

큐에서 pop함과 동시에 정답 체크를 했다. 

 

근데 이렇게 하니까 알고리즘 실행 시간이 제출자 61명 중에 56등이었다.

pypy는 아예 되지도 않았고...

귀찮아서 일단 통과한 것에 의의를 뒀는데, 아마 이런 방법 말고 다른 방법이 있을 것 같다.

그게 아니면 내가 구현을 이상하게 했거나 아무튼

---

2. 코드

 

 

import sys
from collections import deque


def ans(s_a, s_b, s_c):
    if 'C' in s_a or 'B' in s_a:
        return False
    elif 'A' in s_b or 'C' in s_b:
        return False
    elif 'A' in s_c or 'B' in s_c:
        return False
    return True


def sol():
    stack = [sys.stdin.readline().strip()[2:] for _ in range(3)]
    check = set()
    dq = deque()
    dq.append([*stack, 0])
    while dq:
        s_a, s_b, s_c, cnt = dq.popleft()
        if ans(s_a, s_b, s_c):      # 정답인지 확인
            return cnt
        else:
            temp = s_a + '.' + s_b + '.' + s_c      # 방문 표시를 위한 스트링
            if temp not in check:
                check.add(temp)     # 방문 표시
                # 아래는 전부 하나하나씩 큐에 집어넣는 과정
                if len(s_a) != 0:
                    dq.append((s_a[:-1], s_b + s_a[-1], s_c, cnt + 1))
                    dq.append((s_a[:-1], s_b, s_c + s_a[-1], cnt + 1))
                if len(s_b) != 0:
                    dq.append((s_a, s_b[:-1], s_c + s_b[-1], cnt + 1))
                    dq.append((s_a + s_b[-1], s_b[:-1], s_c, cnt + 1))
                if len(s_c) != 0:
                    dq.append((s_a, s_b + s_c[-1], s_c[:-1], cnt + 1))
                    dq.append((s_a + s_c[-1], s_b, s_c[:-1], cnt + 1))


print(sol())

---

3. 마무리

 

 

이건 스터디때 다른 애들 얘기를 들어봐야겠다.