[백준] 단계별로 풀어보기(단계:10,재귀,JAVA)11729번, 하노이 탑 이동 순서

문제 링크

11729번: 하노이 탑 이동 순서

 

www.acmicpc.net

 

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

하노이 탑 이동 횟수를 구하는 공식은 2ⁿ-1입니다.

n개의 블럭이 있는 하노이탑을 이동하는 것은 n-1만큼의 블럭을 가운데에 이동시킨 후 가장 큰 블럭을 목표구역에 이동시킨 뒤 가운데에 있는 n-1에 있는 블럭들을 다 목표구역에 이동시키면 모든 블럭이 목표구역에 이동된다.

알고리즘으로 본다면

1. n-1개를 거쳐가는 구역으로 옮긴다.
2. 남은 가장 큰 블럭을 목표지역에 옮긴다.
3. 거쳐가는 구역에 있는 n-1개 블럭을 목표지역에 옮긴다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 하노이 탑 이동방향을 구하는 hanoi함수를 만들었습니다.

• 위에 알고리즘을 hanoi에 적용시켰습니다.
• 재귀를 통해서 hanoi함수를 반복하여 블럭에 이동방향을 구하였습니다.

• bw에 함수 결과를 저장하였습니다.
• BufferedWriter를 통해 저장된 결과를 출력하였습니다.

결과 코드

import java.io.*;
public class Main{
	static StringBuilder sb = new StringBuilder();	//이동 방향 저장
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       	//BufferedWriter를 통해 결과 출력
    	int num = Integer.parseInt(br.readLine());	//입력값 저장
    	hanoi(num,1,2,3);
    	bw.write((int)Math.pow(2, num)-1 + "\n");	//반복 횟수 bw에 저장
    	bw.write(sb + "\n");	//이동 방향 bw에 저장
    	bw.flush();
    	bw.close();
    	br.close();	
	}
	public static void hanoi(int num,int start, int mid, int end){//하노이탑 함수
    	if(num==1) {	//가장큰 값 end에 옮기기
    		sb.append(start + " " + end + "\n");
    		return;
    	}
    	hanoi(num-1,start,end,mid);	//n-1개를 mid에 옮기기
    	sb.append(start + " " + end + "\n");
    	hanoi(num-1,mid,start,end); //n-1개를 end에 옮기기
	}
}