나의 기록, 현진록

[Swift] Data Structure recursion / hanoi / 자료구조 순환, 재귀 / 하노이 탑 본문

Programming/Algorithm & Data Structure

[Swift] Data Structure recursion / hanoi / 자료구조 순환, 재귀 / 하노이 탑

guswlsdk 2021. 7. 8. 13:17
반응형

 

 

dbguswls030/Argorithm

Contribute to dbguswls030/Argorithm development by creating an account on GitHub.

github.com

 

 

<하노이 탑의 설명>

더보기

고대 인도의 베나레스에는 세계의 중심이 있고, 그 곳에는 아주 큰 사원이 있었다. 이 사원에는 높이 50cm 정도 되는 다이아몬드 막대 3개가 있는데, 그 중 한 막대에는 천지 창조 때에 신이 구멍이 뚫린 64장의 순금으로 된 원판을 크기가 큰 것부터 아래에 놓이도록 하면서 차례로 쌓아 놓았다. 그리고 신은 승려들에게 밤낮으로 쉬지 않고 한 장씩 원판을 옮기어 빈 다이아몬드 막대 중 어느 한 곳으로 모두 옮겨 놓도록 명령하였다...................................

 

조건

1. 한 번에 하나의 원판만 이동할 수 있다.

2. 맨 위에 있는 원판만 이동할 수 있다.

3. 크기가 작은 원판 위에 큰 원판이 쌓일 수 없다.

4. 중간의 막대를 임시적으로 이용할 수 있으나 앞의 조건들을 지켜야 한다.

 

 

위 조건을 기반으로 A, B, C 3개의 막대와 원판 3개를 A에서 C로 옮기는 과정이다.

 

 

 

 

 

 

해결 방안

A는 from

B는 tmp

C는 to라고 할 때

 

1. from의 맨 밑의 원판을 제외한 나머지 원판을 tmp로 옮긴다.

2. from에 남은 한 개의 원판을 to로 옮긴다.

3. tmp에 원판을 to로 옮긴다.

 

A 막대에 있는 원판들을 C로 옮겨야 할 때 n-1번째까지의 원판을 B에 임시로 옮겨두고 n번째 원판을 C에 옮기면 된다.

 

func hanoi(_ n: Int, _ from: Character, _ tmp: Character, _ to: Character){
    if n == 1{
        print("원판 1을 \(from)에서 \(to)로 옮긴다.")
    }
    else{
        hanoi(n-1, from, to, tmp) //1
        print("원판 \(n)을 \(from)에서 \(to)로 옮깁니다") //2
        hanoi(n-1, tmp, from, to) //3
    }
}

hanoi(4, "A","B","C")

 

 

2번은 if n==1 에서 해결이 되기 때문에 1, 3번만 고민하면 될 것이다.

 

1. from의 맨 밑의 원판을 제외한 나머지 원판을 tmp로 옮긴다.

hanoi(n-1, from, to, tmp)

 

3. tmp에 원판을 to로 옮긴다.

hanoi(n-1, tmp, from, to)

 

 

반응형