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

11729번: 하노이 탑 이동 순서 (acmicpc.net)

11729번: 하노이 탑 이동 순서

 

- 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 

- 각 원판은 반경이 큰 순서대로 쌓여 있다. 

- 이제 수도승들이 다음 규칙에 따라 첫 번째 장데에서  세 번째 장대로 옮기려 한다. 

 

  1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 

  2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것 보다 작아야 한다. 

 

- 이 작업을 수행하는 데 필요한 이동 순서를 출력하는 프로그램 

- 단, 이동횟수는 최소가 되어야 함 

 

입력

- 첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N이 주어짐

 

출력 

- 첫째 줄에 옮긴 횟수 K 출력 

- 두 번째 줄부터 수행 과정을 출력 

- 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데 , 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻 

 

 

풀이 과정 

 

2023.07.27 - [C언어/자료구조] - 5-3장 하노이의 탑

5-3장 하노이의 탑

 

- 1의 3개의 원반을 모두 옮기기 위해서는 먼저 A,B 원반(그룹) 을 2번으로 옮겨야 함

- C 원반을 3번으로 옮긴다. 

- 2에 있는 A,B 원반(그룹)을 3으로 옮긴다. 

 

- 기둥 번호는 정수 1,2,3으로 나타냄

- 기둥 번호의 합이 6이므로 시작 기둥, 목표 기둥이 어느 기둥이더라도 중간 기둥은 6-x-y로 구할 수 있음 

 

move(옮겨야 할 원반의 개수, 시작 기둥의 번호, 목표 기둥의 번호)

 

 

정답 

 

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


public class Main 
{
   static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	
   public static void main(String[] args) throws IOException 
   {
	   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
       int n = Integer.parseInt(br.readLine()); //원판의 개수 
       
       bw.write((int)(Math.pow(2, n)-1)+"\n");
       
       hanoi(n,1,3);
       
       bw.flush();
       bw.close();
	   
   }
   
  
   static void hanoi(int n, int start, int end) throws IOException
   {
         if(n==1)
         {
        	 bw.write(start+" "+end+"\n");
        	 return;
         }
         
         hanoi(n-1,start,6-start-end); //그룹을 시작기둥에서 중간기둥으로 
         bw.write(start+" "+end+"\n");
         hanoi(n-1, 6-start-end, end); //그룹을 중간 기둥에서 목표 기둥으로 
   }
   
   
   
}