하노이탑 (재귀X)

하노이탑 재귀이용하지 않고 풀어보기

하노이탑 플레이

Play Tower of Hanoi

원리

사용자로부터 원반의 개수(n), 출발기둥이름(fr), 보조기둥이름(tmp), 목적기둥이름(to)을 입력받음

기둥 세 개는 각각 A, B, C 리스트로 구현

출력할 때 원반이 어디서 어디로 이동했는지 확인하고 싶어 기둥의 이름들을 리스트의 0번째에 저장

원반의 개수를 입력하면 A라는 리스트에 n부터 1까지 차례대로 추가 (수가 클수록 큰 원반)

출발지(fr)의 원반이 모두 목적지(to)로 옮겨가면 루프 종료. 즉, 목적기둥의 원반 수가 입력받은 원반의 개수보다 작을 경우 while문 반복 (목적기둥리스트의 0번째에 기둥이름을 저장했으므로 요소 총 개수 -1 = 목적기둥에 있는 원반의 수)

원반의 개수(n)가 홀수인지 짝수인지에 따라 목적지 및 출발지가 다름. 하지만 둘 다 3개의 동작 반복 (op%3 이용)

 

n이 홀수일 때 아래의 세 동작 반복

1.  A → C
2.  A → B
3.  C → B

n이 짝수일 때 아래의 세 동작 반복

1. A → B
2. A → C
3. B → C

세 동작이 반복하되 각 동작에서 ① fr에 옮길 원반이 없거나 ② to에 원반이 있을 경우 가장 끝의 원반이 fr에서 옮긴 원반보다 작을 경우에는 방향이 반대로 전환(←)

 

def hanoi_tower(n, fr, tmp, to):

    # 0번째에는 유저가 입력한 매개변수 이름을 그대로 저장 => 리스트에는 기본적으로 1개의 요소가 있음
    A = [fr]
    B = [tmp]
    C = [to]

    for i in range(n, 0, -1):
        A.append(i)

    op = 0
    while (len(C)-1 < n):   # n이 홀수인지 짝수인지에 따라 fr과 to가 다름
        op += 1     # 3개의 동작 반복

        if n % 2 == 1:
            # n이 홀수일 때 (아래의 1~3 반복)
            # 1. A->C
            # 2. A->B
            # 3. C->B

            if op % 3 == 1:  # 1. A -> C
                fr = A
                to = C

                # 조건 : A에서 C로 옮길 상황이 안될 경우(A에 원반이 없거나 | C에 원반이 있을 때 A의 끝 값이 C의 끝 값보다 클 때) 방향 전환 (C -> A)
                if (len(A) == 1 or (len(C) > 1 and (A[len(A)-1] > C[len(C)-1]))):
                    fr = C
                    to = A

                to.append(fr.pop(len(fr)-1))
                print("원판 %d: %s --> %s" % (to[len(to)-1], fr[0], to[0]))

            elif op % 3 == 2:  # 2. A -> B
                fr = A
                to = B

                # 조건 : A에서 B로 옮길 상황이 안될 경우(A에 원반이 없거나 | B에 원반이 있을 때 A의 끝 값이 B의 끝 값보다 클 때) 방향 전환 (B -> A)
                if (len(A) == 1 or (len(B) > 1 and (A[len(A)-1] > B[len(B)-1]))):
                    fr = B
                    to = A

                to.append(fr.pop(len(fr)-1))
                print("원판 %d: %s --> %s" % (to[len(to)-1], fr[0], to[0]))

            elif op % 3 == 0:  # 3. C -> B
                fr = C
                to = B

                # 조건 : C에서 B로 옮길 상황이 안될 경우(C가 비어있거나 | B에 원반이 있을 때 C의 끝 값이 B의 끝 값보다 클 때) 방향 전환 (B -> C)
                if (len(C) == 1 or (len(B) > 1 and (C[len(C)-1] > B[len(B)-1]))):
                    fr = B
                    to = C

                to.append(fr.pop(len(fr)-1))
                print("원판 %d: %s --> %s" % (to[len(to)-1], fr[0], to[0]))

        else:
            # n이 짝수일 때 (아래의 1~3 반복)
            # 1. A->B
            # 2. A->C
            # 3. B->C

            if op % 3 == 1:  # 1. A -> B
                fr = A
                to = B

                # 조건 : A에서 B로 옮길 상황(A에 원반이 없거나 | B에 원반이 있을 때 A의 끝 값이 B의 끝 값보다 클 때)이 안될 경우 방향 전환 (B -> A)
                if (len(A) == 1 or (len(B) > 1 and (A[len(A)-1] > B[len(B)-1]))):
                    fr = B
                    to = A

                to.append(fr.pop(len(fr)-1))
                print("원판 %d: %s --> %s" % (to[len(to)-1], fr[0], to[0]))

            elif op % 3 == 2:  # 2. A -> C
                fr = A
                to = C

                # 조건 : A에서 C로 옮길 상황이 안될 경우(A에 원반이 없거나 | C에 원반이 있을 때 A의 끝 값이 C의 끝 값보다 클 때) 방향 전환 (C -> A)
                if (len(A) == 1 or (len(C) > 1 and (A[len(A)-1] > C[len(C)-1]))):
                    fr = C
                    to = A

                to.append(fr.pop(len(fr)-1))
                print("원판 %d: %s --> %s" % (to[len(to)-1], fr[0], to[0]))

            elif op % 3 == 0:  # 3. B -> C
                fr = B
                to = C

                # 조건 : B에서 C로 옮길 상황이 안될 경우(B에 원반이 없거나 | C에 원반이 있을 때 B의 끝 값이 C의 끝 값보다 클 때) 방향 전환 ( C -> B)
                if (len(B) == 1 or (len(C) > 1 and (B[len(B)-1] > C[len(C)-1]))):
                    fr = C
                    to = B

                to.append(fr.pop(len(fr)-1))
                print("원판 %d: %s --> %s" % (to[len(to)-1], fr[0], to[0]))


hanoi_tower(4, 'A', 'B', 'C')

 

원반이 4개일 때 실행 결과