[백준] 11729

당당·2023년 5월 21일

11729 백준

백준

목록 보기

116/179

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

📔문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라.
단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

📝입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

📺출력

첫째 줄에 옮긴 횟수 K를 출력한다.

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

📝예제 입력 1

📺예제 출력 1

🔍출처

-문제를 만든 사람: baekjoon
-빠진 조건을 찾은 사람: hayman42

🧮알고리즘 분류

재귀

📃소스 코드

import java.util.Scanner;
import java.util.Stack;

public class Code11729 {
    public static int N;
    public static StringBuilder sb=new StringBuilder();
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        N=sc.nextInt();

        sb.append(String.valueOf((int)Math.pow(2,N)-1)+"\n");

        Hanoi(N,1,2,3);
        System.out.println(sb);
    }

    public static void Hanoi(int n,int from, int place,int to){
        if(n==1){
            sb.append(from+" "+to+"\n");
            return;
        }

        //N개를 옮기려면 N-1개를 2번째로 옮긴 후
        //제일 마지막 판을 3번째로 옮긴다
        //다시 N-1개의 판을 3번째로 옮긴다
        Hanoi(n-1,from,to,place);
        sb.append(from+" "+to+"\n");
        Hanoi(n-1,place,from,to);
    }

}

📰출력 결과

📂고찰

https://ko.wikipedia.org/wiki/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98_%ED%83%91

하노이의 탑은 3가지 단계로 구성될 수 있다.

N개를 옮기려면 N-1개를 2번째로 옮긴다.
제일 마지막 판을 3번째로 옮긴다
다시 N-1개의 판을 3번째로 옮긴다

처음에는 스택에 넣고 빼는식으로 풀었는데, 하다보니 너무 노가다를 하는 것 같았다. 그래서 하노이의 탑에 대해 알아보았는데, 재귀함수로 아주 유명한 녀석이었다.

public static void Hanoi(int n,int from, int place,int to){

  if(n==1){
      sb.append(from+" "+to+"\n");
      return;
  }

  Hanoi(n-1,from,to,place);
  sb.append(from+" "+to+"\n");
  Hanoi(n-1,place,from,to);
}