[백준] 11729 : 하노이 탑 이동 순서 JAVA 풀이

 

이 문제 또한 손으로 직접 N = 3일 경우를 따라 써봤지만 코드를 어떻게 짜야 할지 감이 안왔다.

하하 ㅋㅋㅋㅋ ㅜㅜ

하지만 바로 다른 사람이 짠 코드를 찾아보긴 아쉬워서 하노이탑의 알고리즘부터 공부를 해보자! 하고

서치를 해봤는데 아주아주아주 좋은 글을 찾았다.

 

https://shoark7.github.io/programming/algorithm/tower-of-hanoi

'하노이의 탑' 이해하기

함수에 어떤 인자가 왜 필요한 것인지 자세히 쓰여있어서 정말 이해하기 쉬웠다.

 

장대 A, B, C가 있고 원판 3개를 A에서 C로 옮겨야 할 때

 

C의 가장 아래에는 3번 원판이 와야 한다.

하지만 그러기 위해서는 그 전에 1번, 2번 원판을 B에 옮겨두어야 한다.

B에 1번, 2번 원판을 옮겨두고

C에 3번 원판을 옮겼으면 다시 B에 있는 1번, 2번 원판을 C로 가져와야 한다.

그러기 위해서는 1번, 2번 원판을 A를 경유해서 C로 옮겨와야 한다.

 

N개의 원판을 A에서 C로 옮기는 과정을 다시 정리하면 이렇게 된다.

1. N번 원판 위의 N-1개의 원판을 출발지(A)에서 경유지(B)로 옮긴다.

2. N번 원판을 도착지(C)로 옮긴다.

3. 경유지(B)에 있는 N-1개의 원판을 다시 도착지(C)로 옮긴다.

 

옮겨야 할 원판이 한 개밖에 없을 때는 그저 출발지에서 도착지로 움직이면 되기 때문에,

이때가 재귀를 종료하는 시점이 된다.

 

따라서 함수의 형태는

hanoi(옮길 원판의 개수, 출발지, 도착지, 경유지)가 된다.

원판의 개수가 1일 때는 출발지, 도착지를 출력하고 함수를 종료하고,

그렇지 않을 때는 다시 재귀를 하면 된다.

 

 

위 포스트를 참고해서 작성한 코드는 다음과 같다.

옮길 원판이 1개일 때마다 System.out.println()를 매번 호출하는 식으로 했더니

시간 초과가 나와서 StringBuilder를 사용했다.

 

하노이 알고리즘의 최소 이동 횟수는 (2^N)-1이라 

java.lang.Math 클래스에 있는 Math.pow(밑, 지수)로 계산해 출력해줬다.

 

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.lang.Math;
public class Main{
    public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        System.out.println((int)(Math.pow(2, N)-1));
        hanoi(N, 1, 3, 2);
        System.out.print(sb);
    }
    public static void move(int n, int from, int to){
        sb.append(from).append(" ").append(to).append('\n');
    }
    public static void hanoi(int n, int from, int to, int via){
        if(n==1){
            move(n, from, to);
            return;
        }
        else{
            hanoi(n-1, from, via, to);
            move(n, from, to);
            hanoi(n-1, via, to, from);
        }
    }
}

이렇게 짜놓고 보니, move 함수에서 하는 일이 결국 스트링빌더에 값을 추가하는 것뿐이라

함수를 지우고, move함수를 호출하는 부분에 스트링빌더에 값을 추가하는 문장을 넣었다.

 

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.lang.Math;
public class Main{
    public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        System.out.println((int)(Math.pow(2, N)-1));
        hanoi(N, 1, 3, 2);
        System.out.print(sb);
    }
    public static void hanoi(int n, int from, int to, int via){
        if(n==1){
            sb.append(from).append(" ").append(to).append('\n');
            return;
        }
        else{
            hanoi(n-1, from, via, to);
            sb.append(from).append(" ").append(to).append('\n');
            hanoi(n-1, via, to, from);
        }
    }
}