[자바] 11729번 하노이 탑 이동

문제

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

 

코드 리뷰

맨 처음에 System.out.println()으로  여러번 출력을 하다가 시간초과가 났다. 그래서 StringBuilder를 사용하여 문자열을 계속 붙여준뒤에 메인함수 마지막에서 System.out.println()을 한 번 호출했다. 입력은 BufferedReader를 사용했다. 

변수 num에는 원판의 수를 입력받아 저장한다.  sb는 메인 메소드 안에서 선언하지 않고 한 단계 위에서 선언해서 다른 메소드에서도 접근할 수 있도록 했다.

 

변수 count에는 원판의 총 이동 횟수를 저장한다. 하노이 탑에서 원판의 총 이동횟수는 원판의 갯수가 n이라 할 때 2^n -1이다. 이때 Math.pow()를 사용하는데 입력값과 반환값 모두 double형이다. 따라서 앞에 (int)를 붙여준다.

 

append를 연속적으로 사용하여 가독성을 높였다.

movePlate는 재귀함수이다. 우리의 목적은 num 갯수의 원판을 1에서 3으로 옮기는 것이다. 이따 다른 위치는 other을 의미한다.

 

하노이 문제의 해결은 재귀함수이다. 재귀함수는 메소드 안에서 다시 메소드를 호출하는 구조이다. 그렇기 때문에 탈출할 수 있는 조건이 없으면 무한히 계속 들어가기 때문에 탈출 조건을 만들어야 한다. 원판의 갯수가 0이면 탈출을 할 수 있도록 조건을 걸었다.

 

n개의 원판을 1에서 3으로 옮기려면 우선적으로 가장 큰 원판위에 있는 n-1원판을 2로 옮겨야 한다. 그리고 가장 큰 원판을 3으로 옮기고 마지막으로 2에 있는 n-1개의 원판을 3으로 옮긴다. 즉 크게보면 3단계로 나눠진다.

 

moveplate(num-1,from, to, other)은 가장 큰 원판을 제외하고 나머지 원판들을 2로 옮기는 행위를 의미한다.

sb.append(form)~는 가장 큰 원판을 1에서 3으로 옮기는 것을 의미한다.

moveplate(num-1,other, from, to)는 가운데로 옮겨진 원판을 3으로 옮기는 행위를 의미한다.

 

코드

package 백준.재귀.하노이탑_11729;

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

public class 하노이탑_11729 {
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int count = (int)Math.pow(2, num) - 1;

        sb.append(count).append("\n");
        movePlate(num,1,2,3);
        System.out.println(sb);
    }

    public static void movePlate(int num, int from, int other, int to) {

        if(num == 0)
            return;

        movePlate(num-1, from, to, other);
        sb.append(from).append(" ").append(to).append("\n");
        movePlate(num-1,other, from, to);
    }
}