하노이의 탑

하노이의 탑
연습문제
1186명 완료

워낙 유명한 문제라... 

https://programmers.co.kr/learn/courses/30/lessons/12946

코딩테스트 연습 - 하노이의 탑

일단 종이로 어떤 식으로 움직이는지 확인해도 좋겠지만..
종이보다 컴이 편해서..

n = 2인 경우... 

def solution(n):
    tower = [[i for i in range(n, 0, -1)], [], []]
    print(tower)

    def move(f, t):  # f 는 from, t 는 to
        if tower[t] and tower[f][-1] > tower[t][-1]:
            raise Exception('큰 원판이 작은 원판 위에 올라갑니다.')
        tower[t].append(tower[f].pop())
        print(tower)

    def m2():
        move(0, 1)
        move(0, 2)
        move(1, 2)

    m2()

solution(2)

[[2, 1], [], []]
[[2], [1], []]
[[], [1], [2]]
[[], [], [2, 1]]

n = 3인 경우

def solution(n):
    tower = [[i for i in range(n, 0, -1)], [], []]
    print(tower)

    def move(f, t):
        if tower[t] and tower[f][-1] > tower[t][-1]:
            raise Exception('큰 원판이 작은 원판 위에 올라갑니다.')
        tower[t].append(tower[f].pop())
        print(tower)
    
    def m2():
        move(0, 1)
        move(0, 2)
        move(1, 2)
    
    def m3():
        move(0, 2)
        move(0, 1)
        move(2, 1)
        move(0, 2)
    #     m2()

    m3()

solution(3)

[[3, 2, 1], [], []]
[[3, 2], [], [1]]
[[3], [2], [1]]
[[3], [2, 1], []]
[[], [2, 1], [3]]

여기서 m2 함수를 바로 써먹으려고 하니 안된다 ㅠ,.ㅠ 

m2 함수를 매개변수를 사용하도록 바꿔주자. 

    def m2(f, t, temp):
        move(f, temp)
        move(f, t)
        move(temp, t)

하는 김에 m3 함수도 바꿔주자. 

    def m3(f, t, temp):
        m2(f, temp, t)
        # move(f, t)
        # move(f, temp)
        # move(t, temp)
        move(f, t)
        m2(temp, t, f)

바꾸다 보니 공통점을 찾았다. 재귀로 바꿔줘야겠다. 테스트도... 

일단 테스트... n이 3일 때

def solution(n):
    tower = [[i for i in range(n, 0, -1)], [], []]
    print(tower)

    def move(f, t):
        if tower[t] and tower[f][-1] > tower[t][-1]:
            raise Exception('큰 원판이 작은 원판 위에 올라갑니다.')
        tower[t].append(tower[f].pop())
        print(tower)

    def m2(f, t, temp):
        move(f, temp)
        move(f, t)
        move(temp, t)

    def m3(f, t, temp):
        m2(f, temp, t)
        move(f, t)
        m2(temp, t, f)

    m3(0, 2, 1)

solution(3)

[[3, 2, 1], [], []]
[[3, 2], [], [1]]
[[3], [2], [1]]
[[3], [2, 1], []]
[[], [2, 1], [3]]
[[1], [2], [3]]
[[1], [], [3, 2]]
[[], [], [3, 2, 1]]

n이 4일 때

def solution(n):
    tower = [[i for i in range(n, 0, -1)], [], []]
    print(tower)

    def move(f, t):
        if tower[t] and tower[f][-1] > tower[t][-1]:
            raise Exception('큰 원판이 작은 원판 위에 올라갑니다.')
        tower[t].append(tower[f].pop())
        print(tower)

    def m2(f, t, temp):
        move(f, temp)
        move(f, t)
        move(temp, t)

    def m3(f, t, temp):
        m2(f, temp, t)
        move(f, t)
        m2(temp, t, f)

    def m4(f, t, temp):
        m3(f, temp, t)
        move(f, t)
        m3(temp, t, f)

    m4(0, 2, 1)

solution(4)

[[4, 3, 2, 1], [], []]
[[4, 3, 2], [1], []]
[[4, 3], [1], [2]]
[[4, 3], [], [2, 1]]
[[4], [3], [2, 1]]
[[4, 1], [3], [2]]
[[4, 1], [3, 2], []]
[[4], [3, 2, 1], []]
[[], [3, 2, 1], [4]]
[[], [3, 2], [4, 1]]
[[2], [3], [4, 1]]
[[2, 1], [3], [4]]
[[2, 1], [], [4, 3]]
[[2], [1], [4, 3]]
[[], [1], [4, 3, 2]]
[[], [], [4, 3, 2, 1]]

5일 때도 확인은 했는데 분량 관계로...... 

코드를 보면 m3 함수부터는 공통적인 부분이 있어 재귀가 성립하는데
m2는 안되니까 리턴을 해야 할 포인트 임을 알 수 있다. 
리턴을 위한 매개변수를 하나 더 추가하자. 

def solution(n):
    answer = []
    tower = [[i for i in range(n, 0, -1)], [], []]

    def move(f, t):
        tower[t].append(tower[f].pop())
        answer.append([f + 1, t + 1])

    def m2(f, t, temp):
        move(f, temp)
        move(f, t)
        move(temp, t)

    def hanoi(f, t, temp, time):
        if time == 2:
            m2(f, t, temp)
            return
        hanoi(f, temp, t, time - 1)
        move(f, t)
        hanoi(temp, t, f, time - 1)

    hanoi(0, 2, 1, n)

    return answer

조금 더 정리..

def solution(n):
    def move(f, t):
        tower[t].append(tower[f].pop())
        answer.append([f + 1, t + 1])

    def hanoi(f, t, temp, time):
        if time == 2:
            move(f, temp)
            move(f, t)
            move(temp, t)
            return
        hanoi(f, temp, t, time - 1)
        move(f, t)
        hanoi(temp, t, f, time - 1)

    answer = []
    tower = [[i for i in range(n, 0, -1)], [], []]
    hanoi(0, 2, 1, n)

    return answer

정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.7MB)
테스트 2 〉	통과 (0.05ms, 10.7MB)
테스트 3 〉	통과 (0.06ms, 10.8MB)
테스트 4 〉	통과 (0.08ms, 10.7MB)
테스트 5 〉	통과 (0.09ms, 10.9MB)
테스트 6 〉	통과 (0.16ms, 10.7MB)
테스트 7 〉	통과 (0.32ms, 10.8MB)
테스트 8 〉	통과 (0.62ms, 11.1MB)
테스트 9 〉	통과 (1.16ms, 12MB)
테스트 10 〉	통과 (2.57ms, 16.7MB)
테스트 11 〉	통과 (5.12ms, 26.2MB)
테스트 12 〉	통과 (9.95ms, 45MB)
테스트 13 〉	통과 (19.68ms, 82.5MB)

이 정도면 설명과 함께한 것치곤 잘 코딩된 것 같고.. 

실전에서는 숫자에 집중한다면 더 깔끔하게 코딩할 수 있다. 

def solution(n):
    return hanoi(n, 1, 3, [])


def hanoi(n, f, t, answer):
    if n == 0:
        return
    temp = 6 - f - t
    hanoi(n - 1, f, temp, answer)
    answer.append([f, t])
    hanoi(n - 1, temp, t, answer)
    return answer

정확성  테스트
테스트 1 〉	통과 (0.04ms, 10.7MB)
테스트 2 〉	통과 (0.05ms, 10.7MB)
테스트 3 〉	통과 (0.05ms, 10.7MB)
테스트 4 〉	통과 (0.06ms, 10.6MB)
테스트 5 〉	통과 (0.09ms, 10.8MB)
테스트 6 〉	통과 (0.14ms, 10.8MB)
테스트 7 〉	통과 (0.33ms, 10.9MB)
테스트 8 〉	통과 (0.54ms, 10.9MB)
테스트 9 〉	통과 (1.06ms, 12MB)
테스트 10 〉	통과 (2.26ms, 16.6MB)
테스트 11 〉	통과 (4.46ms, 26.2MB)
테스트 12 〉	통과 (8.91ms, 44.8MB)
테스트 13 〉	통과 (17.76ms, 82.6MB)

좀 더 정리한다면.... 

매개변수(parameter)에 초깃값 지정하기
https://dojang.io/mod/page/view.php?id=2348

def solution(n, source=1, destination=3, answer=[]):
    if n == 0:
        return
    temp = 6 - source - destination
    solution(n - 1, source, temp, answer)
    answer.append([source, destination])
    solution(n - 1, temp, destination, answer)
    return answer

나에겐 꽤 의미 있는 문제.
프로그래밍에 빠졌던 고등학교 시절.
서점에서 이 문제를 보고선
흥미를 가졌었는데.. 
프로그래밍을 열심히 할 상황은 아니라..
대학가서 풀어야 겠다.. 라고.. 미뤘었다..

그런데 컴퓨터와
전혀 관련없는 과에 진학하면서.. 
이 문제를 잊고 지내다가.. 
이제야 풀게 되었다.. 

그때 또 하나 미룬 게 
민맥스 알고리듬을 기반으로한 
세균전 게임 만들기...