티스토리 뷰

728x90
:D 문제

문제

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

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

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

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

입력

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

출력

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

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

Baekjoon

 

11729번: 하노이 탑 이동 순서

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

www.acmicpc.net

 
:D 풀이 방법

예제와 같이 기둥 1, 2, 3이 존재할 때, N개의 원판을 옮긴다면

N-1개의 원판을 현재 경유지인 2번 기둥으로 옮기고, N번째 원판을 최종 목적지인 3번 기둥으로 옮긴다. 

N번째 원판이 최종 목적지인 3으로 옮겨졌다면, 나머지 N-1개의 원판을 다시 재배치해야 한다.

N-1개의 원판은 현재 2번 기둥이 시작 기둥이 된다. 그럼 1번 기둥이 경유지가 됨으로 N-2개의 원판을 1번 기둥으로 옮긴다. 그리고 N-1번째 원판을 3번으로 옮긴다. 하노이는 이 과정을 반복하여 최종 목적지로 모든 원판을 옮길 수 있다.

 

 
:D 작성 코드

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

public class Solution11729H {
    static StringBuilder answer;
    static int count;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        answer = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        count = 0;
        hanoi(N, 1, 2, 3);
        System.out.println(count);
        System.out.print(answer);
    }

    private static void hanoi(int n, int start, int tmp, int end) {

        // 마지막 하나는 최종 기둥으로 옮긴다.
        if (n == 1) {
            answer.append(start + " " + end + "\n");
            count ++;
            return;
        }

        // n-1개의 원반을 시작 기둥에서 보조 기둥으로 옮긴다.
        hanoi(n - 1, start, end, tmp);
        answer.append(start + " " + end + "\n");
        count ++;

        // 보조 기둥에 있는 원반을 최종 기둥으로 옮긴다.
        hanoi(n - 1, tmp, start, end);
    }
}

 

 

 

마무리

하노이를 코드로 구현하면서 처음에는 조금 헷갈렸다. 여러 번의 시도 끝에 구현할 수 있었지만, 다음에는 헷갈리지 않게 개념을 확실히 정리하고 해봐야겠다.!

728x90
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크