[백준] 11729번 하노이탑

 

[21-04-20]

 

 

분명 배웠던 하노이탑이 새삼 새롭게 느껴졌다...

옛날 옛적 알고리즘 수업 시간에도 하노이탑의 풀이과정은 뭔가 이해가 잘 되지 않았었는데

아마 나는 재귀 자체에 약한가보다...^^^,,, 이번에도 역시,..,,ㅎㅎ

익숙하게 다룰 수 있도록 열공하자,,,^^,,,

 

 

---

 

문제

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

11729번: 하노이 탑 이동 순서

 

 

분석

문제 자체가 이동 횟수도 출력해야 하고 이동 과정도 출력해야 한다.

그럼 함수 어딘가에 출발지 > 목적지와 같은 출력문이 분명히 들어갈 것이다.

또한 무조건 큰 원반이 아래에 위치하고 작은 원반이 위에 있어야 한다. 

 

재귀는 어떤 구간이 반복되어 호출되는지와 기저사례를 찾아야 하기 때문에

직접 옮겨보며 다음과 같은 특징을 파악했다.

 

1. 맨 아래의 원반을 옮기기 위해서는 위에 쌓여있는 원반들이 모두 옮겨져야 한다.

  > 1번 꽂이에 4개의 원반이 꽂혀있으면, 맨 아래 원반을 제외한 3개(N-1)의 원반 이동이 일어나야 한다.

  > N개의 원반을 옮기는데 걸리는 횟수

    = 맨 아래 원반을 제외한 N-1개의 원반을 옮기는 횟수 + 1번(맨 아래 원반 옮기기) + N-1개의 원반을 목적지로 다시쌓는 횟수

  > 목적지에 다시 쌓는 것을 고려하면 N-1개의 원반 이동이 총 2번 일어나는 것을 알 수 있다. (옮겨놓기,다시 쌓기)

2. 원반 2개를 특정 위치로 옮기기 위해서는 다른 꽂이를 이용하여 교환해야 한다. (1개는 바로 이동시키면 됨)

   > 큰 원반이 작은 원반 위로 이동 할 수가 없기 때문에, 중간 지점을 두고 교환한다.

3. 원반 1개 이동이 출력과 같다.

  > 문제 자체가 이동을 출력하는 것이기 때문에 원반이 1개일 때는 다른 액션 없이 출력만 하면 된다.

 

 

알고리즘만 풀면 되지 않을까 싶었는데 왠걸 시간초과가뜬다.,..ㅎㅎㅎ...

찾아보니 System.out을 사용할 경우 시간이 많이 소요된다고 한다..☆

결국 출력문을 BufferWriter로 수정함

 

코드

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Scanner;

public class Main {
	
	// 시간 때문에 System.out 쓰지 않고 Buffer로 사용
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws IOException {		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		bw.write( (int)Math.pow(2, n) - 1 + "\n" );
		
		hanoi(n, 1, 3, 2);
		
		bw.close();
	}
	
	// n개의 원반이 목적지로 이동하기 위한 이동 내역을 출력하는 함수 
	public static void hanoi(int n, int source, int dest, int other) throws IOException {
		if(n == 1) {
			bw.write(source + " "+ dest + "\n" );	 // 원반이 1개면 바로 출력(옮기는 작업 필요X)
			return;
		} else {
			hanoi(n-1, source, other, dest);
			bw.write(source + " " + dest + "\n" );
			hanoi(n-1, other, dest, source);
		}
	}
	
}

 

 

 

결과

 

 

 

---

추후에 옮기는 과정을 그림으로 추가해야겠다!