백준 11729번: 하노이 탑 이동 순서

문제

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

11729번: 하노이 탑 이동 순서

---

풀이

서로 다른 크기의 원판 n개를 하노이탑 규칙에 맞게 목표지점으로 옮길 때 옮긴 횟수와 수행과정을 출력하는 문제입니다.

원판 이동 과정 설명은 아래 그림으로 대체하겠습니다.

n = 3인 경우

위의 그림을 의사코드로 표현하면 다음과 같습니다.

hanoi(n, from, tmp, to):
    if n = 1이면
        then from의 맨 위에 있는 원판 1개를 to로 옮김
    else 
        hanoi(n - 1, from, to, tmp)
        from의 맨 위에 있는 원판 1개를 to로 옮김
        hanoi(n - 1, tmp, from, to)

옮긴 횟수를 구하기 위해 위의 과정을 살펴보면 n개의 원판을 옮기는 과정은 n - 1개 원반 옮기는 빨간색, 초록색과 가장 밑의 원반 1개를 옮기는 파란색 과정으로 나눌 수 있고, 총 2 x (n - 1) + 1회입니다. 이 내용을 의사코드로 표현하면 다음과 같습니다.

counting(n):
    if n = 1이면
        then return 1
    else 
        then return 2 * counting(n - 1) + 1

---

코드

C언어

counting 함수를 이용하여 이동 횟수를 먼저 구한 뒤에 hanoi 함수로 이동 과정을 출력합니다.

#include <stdio.h>
int counting(int n) {
    if (n == 1) return 1;
    return 2 * counting(n - 1) + 1;
}
void hanoi(int n, int from, int tmp, int to) {
    if (n == 1) printf("%d %d\n", from, to);
    else {
        hanoi(n - 1, from, to, tmp);
        printf("%d %d\n", from, to);
        hanoi(n - 1, tmp, from, to);
    }
}
main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", counting(n));
    hanoi(n, 1, 2, 3);
}

자바

Stringbuilder를 이용하면 위의 C언어 코드처럼 이동 횟수를 구하기 위해 counting 함수를 따로 만들지 않고 기존에 있던 함수 안에서 횟수를 구하고 문제의 출력 조건에 맞게 먼저 출력할 수 있습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

    static int cnt = 0;
    static StringBuilder sb = new StringBuilder();

    public static void hanoi(int n, int from, int tmp, int to) {
        cnt++;
        if (n == 1) {
            sb.append(from).append(' ').append(to).append('\n');
        } else {
            hanoi(n - 1, from, to, tmp);
            sb.append(from).append(' ').append(to).append('\n');
            hanoi(n - 1, tmp, from, to);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        hanoi(n, 1, 2, 3);
        System.out.println(cnt);
        System.out.print(sb);
    }
}

 

---

결론

이 문제는 다른 문제와 다르게 함수의 매개변수의 위치가 고정이 되어있지 않아서 풀기 어려웠던 기억이 있습니다. 모든 과정을 그린 뒤에 함수 안에 함수가 실행될 때마다의 n과 from, to를 출력해가며 테스트하다 보니 위와 같은 함수를 만들 수 있었고, 문제를 풀 때 그림을 그려가며 해결했을 때의 장점을 알게 되는 좋은 경험이었습니다.