백준 11729 - 하노이 탑

문제 파악

n개의 원판이 작은 것에서 큰 순으로 쌓여있는데, 이 순서 그대로 다른 곳에 옮기는 문제 -> 한 번에 하나씩만 옮길 수 있고, 작은 것 위에 큰 것을 놓지 못함

같은 연산이 계속 반복되므로 재귀 호출을 사용!
예를 들어 원반이 세 개인 경우
1. 1번 원반을 A에서 C로 이동
2. 2번 원반을 A에서 B로 이동
3. 1번 원반을 C에서 B로 이동
4. 3번 원반을 A에서 C로 이동
5. 1번 원반을 B에서 A로 이동
6. 2번 원반을 B에서 C로 이동
7. 1번 원반을 A에서 C로 이동

풀이

원반의 개수가 n개일 때
1. n-1개를 B로 이동
2. 남은 한 개의 원판을 C로 이동
3. n-1개를 C로 이동

이 때, 출발지, 경유지, 도착지가 매번 달라지기 때문에 세 곳을 모두 변수로 받아야 한다!
-hanoi(3, "A", "B", "C") 느낌으로

1. 재귀 호출할 때의 핵심은 base case!
   a. 원반이 하나일 때는 그냥 옮기면 되므로 n == 1이면 리턴
2. 남은 하나의 원반을 출발지에서 도착지로 옮긴다.
   a. 이 때, 스트링버퍼에 출력 값을 다 넣어줄 것이다.

   멀티 스레드 환경에서는 스트링버퍼가 동기화를 지원해(syncronized 키워드로) 안전해서 사용했다.

코드

import java.util.Scanner;

public class 하노이_탑_이동_순서 {
    static int count = 0;
    static StringBuffer stringBuffer = new StringBuffer();

    public static void main(String[] args) {
        //입력을 하나밖에 안받아서 그냥 스캐너를 썼다..
        Scanner sc = new Scanner(System.in);
        //멀티 스레드 환경에서는 스트링버퍼가 스트링빌더 보다 낫다고 한다.

        int N = sc.nextInt();
		
        //출발점 : 1, 도착점 : 3, 경유지 : 2
        hanoi(N, 1, 3, 2);
        System.out.println(count);
        System.out.println(stringBuffer);
        
    }

    public static void hanoi(int n, int fr, int to, int tmp) {
        //base case
        if (n == 1) {
            count++;
            stringBuffer.append(fr + " " + to + "\n");
        } else {
            //n-1개를 경유지로 옮기기
            hanoi(n-1, fr, tmp, to);
            //남은 하나를 시작점에서 도착점으로 옮기기
            stringBuffer.append(fr + " " + to + "\n");
            count++;
            //경유지에 있던 n-1개를 도착점으로 옮기기
            hanoi(n-1, tmp, to, fr);
            
        }
    }
}