백준알고리즘:p11729 하노이 탑 이동 순서

분류: 재귀

 

▶문제

 

▶정답코드

//백준알고리즘 제출시 클래스 이름은 Main으로 바꿔야 됨 
package recursion;

import java.util.Scanner;

public class p11729_hanoi {
//하노이탑.
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sb.append((int)Math.pow(2,n)-1+"\n");//Math.pow는 실수로 나옴
		hanoi(n, 1, 2, 3);
		System.out.print(sb);

		sc.close();
	}

	public static void hanoi(int n, int start, int mid, int to) {
		if(n==1) {
			sb.append(start+" "+to+"\n");
			return;
		}
	//start 이동하려는 원판의 현위치, mid 거쳐가는 곳, to는 최종적으로 옮겨져야 하는 곳
		hanoi(n-1, start, to, mid);//n-1개를 A에서 B로 이동 A:출발지 C:거치는곳 B:도착지
		sb.append(start+" "+to+"\n");//n+1번째를 A에서 C로 이동 
		hanoi(n-1, mid, start, to);//n-1개를 2번에서 3번으로 이동 B출발 A지나쳐서 C로 도착
	}
}

▶재귀를 사용해서 풀어야 한다.

작은 원판이 큰 원판 밑에 있으면 안된다.

n+1개의 원판이 있을때, n개를 2번에 옮기고

n+1번째를 3에 옮기고, n개를 3번쨰에 옮긴다.

마찬가지로 n개를 옮길 땐, n을 먼저 C로 옮기고 n-1개를 C로 올긴다고 생각하면 된다.

▶ 먼저 하노이탑의 이동 횟수를 구해보자. 

원판이 3개 일때

1->3  1->2  3->2  1->3  2->1  2->3  1->3

7번

참고한 블로그  st-lab.tistory.com/96

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

→하노이탑 이동 횟수와 이동 순서를 구하는 법이 잘 설명 되어있다ㅠ

 

 

▶알아보기 쉽게 start mid to대신 A B C를 넣어서 해보았다.

package recursion;

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

//하노이탑 연습
public class hanoi {
public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		move(n, 1, 2, 3);
		
		try(BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));){
			bw.write(String.valueOf(sb));
		}catch (Exception e) {e.printStackTrace();};
		
		sc.close();
	}
//ABC로 표현하니까 더 이해가 잘간다.
	public static void move(int n, int A, int B, int C) {//A자리는 현재 자리from, B자리는 통과하는 자리via, C자리는 최종도착 자리to
		if(n==1) {
			sb.append(A+"->"+C+"\n");
			return;//리턴 빼먹으면 안됨!!!
		}
		move(n-1, A, C, B);//1. n개를 A->B로 옮기기
		sb.append(A+"->"+C+"\n");//2. n+1번쨰를 A->C로 옮기기
		move(n-1, B, A, C);//3. n개를 B->C로 옮기기
	}
}

 

▶이 문제는 이해했는데 다음에 보면 헷갈리는 문제같다... 이번에 정확히 해놓고 가자

 

---

채점결과

Scanner와 StingBuilder를 사용했다. 출력은 그냥 print로

Math.pow()는 실수를 반환해서 int형으로 바꿔줘야 정답이 된다. 

 

링크 www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서