[백준] 11729번 하노이 탑 이동 순서 -자바(JAVA)

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

11729번: 하노이 탑 이동 순서

망할 하노이탑을 리뷰할 시간이다. 덕분에 머리에 과부하가 제대로 걸렸다.

백준에서 단계별로 풀어보기를 따라서 풀어보고 있던 터라, 재귀 함수를 이용하는 문제인 줄은 알고 시작했다.

어릴때 모형으로 여러번 가지고 놀았던 기억이 있는데, 도대체 이걸 어떻게 코드로 구현하란건지 막막했다.

 

그러곤 한창 스트레스 받으며 화장실에 앉아있었는데, 갑자기 머리에 스쳐지나간 생각이 있다.

"도대체 이걸 내가 왜 고민하고 있어야 하지? 컴퓨터가 알아서 해주면 되는거 아닌가?"

"어떻게든 넘기면 뒷처리는 컴퓨터가 알아서 해주지 않을까?"

 

그래서 일단 유사한 패턴을 찾아보고자 열심히 그림을 그렸다.

아이고 힘들다

그림을 그리면서 얻은 패턴은 다음과 같다.

• 원판이 N개라면, 옮긴 횟수는 2^N-1번이다.
• 원판이 홀수개라면 첫 이동은 1->3, 원판이 짝수개라면 첫 이동은 1->2이다.
• (원판이 N개일때, 2^N-1번째 상황에서 세번째 장대와 두번째 장대가 바뀌고, 첫번째 장대에 숫자N이 적힌 원판이 놓인 상황) = (원판이 N+1개일때, 2^N-1번째 상황)
• 각 단계별로 1번째, 3번째, 7번째, 15번째.... 상황에 주목해보면, 탑이 일정한 규칙으로 쌓이는 것을 알 수 있다.(모두 2의 제곱수-1번째 상황으로, 위의 패턴의 확장임)

 

세번째 패턴 예시

네번째 패턴 예시

 

여기서 나는 네번째 패턴에 주목해 보기로 결정했다.

 

이제 최대한 나의 머리가 아닌 컴퓨터가 일을 할 수 있도록 만들기 위한 생각을 시작했다.

재귀함수를 언제 return 시킬까? 당연히 움직일 원판이 없을 때지!

움직일 원판이 없음은 어떻게 알 수 있지? 그러게 뭔가 함수 인자를 받아야 겠다! 어떤 인자를 받아야하지?

컴퓨터에게 뒷일를 맡기기 위해선 어떤 인자들을 넘겨야 하지? 그러게...일단 N개의 원판을 어느 장대에서 어느 장대로 넘기고 싶은지 알려주면 되지 않을까..?

 

4단계로 예를 들어 생각해보자.

나는 컴퓨터에게 4개의 원판을 1번 장대에서 3번 장대로 넘기고 싶다고 말할 것이다. 

 

그러면 컴퓨터는 7번째 상황이 되기 위해서 원판1,2,3을 2번째 장대에 쌓아야 하고, 다음 상황으로 넘어가기 위해서 원판4를 3번 장대로 넘긴 후, 원판3개를 3번 장대의 원판4위에 쌓아야 한다.

 

마찬가지로....

컴퓨터는 3번째 상황이 되기 위해 원판 1,2를 3번 장대에 쌓아야 하고, 다음 상황으로 넘어가기 위해 원판3을 2번 장대로 넘긴 후, 그 위에 원판2와 1을 쌓아야 한다.

 

그러기 위해선, 또 컴퓨터는 우선 1번째 상황이 되기 위해 원판 1를 2번 장대로 넘긴 후, 다음 상황으로 넘어가기 위해 원판2를 3번 장대로 넘긴 후, 그 위에 원판1을 쌓아야 한다. 

 

무엇보다도 제일 먼저 일어나야 할 일은, 첫번째 상황에서 원판 4321순서로 쌓여 있을 때, 원판 1이 이동해야 하는 것!

 

일반화하면, K개의 원반을 옮기기 위해선 반드시 아래의 세 상황을 거쳐야 한다.

2^K-1-1 번째 상황 -> 파란색 하이라이트 *K-1개의 원반이 2번/3번 장대에 쌓여있고 1번 장대에 K가 적힌 원반만 있음

2^K-1 번째 상황 -> 노란색 하이라이트 *K가 적힌 원반이 1번 장대에서 3번/2번 장대로 넘어간 상황

2^K -1 번째 상황 -> 주황색 하이라이트 *K개의 원반이 모두 3번/2번 하나의 장대에 잘 쌓여진 상황

 

설명이 거지같아도..어쩔수 없다 이것이 나의 최선...

어쨌든 위와 같은 과정을 거치기 위한 hanoi() 재귀 함수를 만들었다.

	public static void hanoi(int N, int from, int to, int tmp) {
		if(N == 0) { //넘길 원판 없으므로 재귀 호출의 끝
			return;		
		}else{
			hanoi(N-1, from, tmp, to); //파란색 하이라이트, 2^(N-1)-1번째 상황으로 만들기 위한 조건
			sb.append(from + " " + to + "\n");//노란색 하이라이트, 2^(N-1)번째 상황, 위아래 두 상황사이에서 N이 적힌 원판의 이동
			cnt++;
			hanoi(N-1, tmp, to, from);//주황색 하이라이트, 2^(N)-1 번째 상황으로 가기 위한 조건
		}
	}

 

그리고 나머지 연산은 컴퓨터에게 맡겼더니 잘 통과 하더라^^ㅋㅋ

혹시 본인이 만든 하노이가 잘 돌아가는지 확인하고 싶다면, 출력값이 2의 제곱수 -1 인지 확인해 보면 된다.

import java.io.*;
import java.util.*;

public class Main {
	static int cnt = 0;
	static StringBuilder sb = new StringBuilder();
	public static void hanoi(int N, int from, int to, int tmp) {
		if(N == 0) { 
			return;		
		}else{
			hanoi(N-1, from, tmp, to);
			sb.append(from + " " + to + "\n");
			cnt++;
			hanoi(N-1, tmp, to, from);
		}
	}
	
	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, 3, 2);
		
		System.out.println(cnt);
		System.out.println(sb);
	}
}