백준 하노이탑 2270 Java (Gold 1)

문제 요약
이 문제는 하노이탑 변형문제이다.
기존의 하노이탑은 3번 막대기에 하노이탑을 쌓으면 된다.
하지만 이 문제에선, 각 막대기에 디스크가 크기순대로 놓여져있는 상황에서 원하는 막대기에 최소비용으로 1-n 번 디스크를 놓으면 된다.
 

• 입력:
  • n: 디스크 개수 (1 ≤ n ≤ 100,000)
  • a, b, c:  차례로 1, 2, 3번 막대기에 꽂혀 있는 디스크의 개수 (0 ≤ a,b,c ≤ n )
  • 3줄에 걸쳐서, 각 막대기에 꽂혀있는 디스크들의 번호가 주어진다.
• 출력:
  • 첫째 줄에 모아야 하는 막대기의 번호(1, 2, 3 중 하나)을 return한다.
  • 최소의 이동 횟수를 1,000,000으로 나눈 나머지를 return한다

접근 방식

n=4 라고한다면 기존 하노이탑은 아래 상황에서

 
이와 같이 3번 막대기로 이동해야한다. 
그러나 이번 문제에서는 최종 막대기의 번호가 자유롭기 때문에 마지막 디스크가 이미 놓여져있는 막대기를 최종막대기로 게임을 진행하면 
이동 횟수를 최소화 할 수있다.
따라서 n번 디스크가 2번 막대기가 있으면 k=2가 되는 것이다  

 
 
 
기존 하노이탑의 재귀방법에 대해서 가볍게 설명하면,
start->end라고 옮겨야되는 상황에서 1~ n-1 디스크를 start->via로 피신(?)시키고
n번 막대기를 start->end로 이동시키고
1~ n-1 디스크를 다시 via-> end로 옮기면된다.
 

 public static void move(int num,int start, int end, int via) {
		 if(num==1) {
			 sb.append(start+" "+ end+"\n");
		 }else {
			 move(num-1,start,via,end);
			 sb.append(start+" "+end+"\n");
			 move(num-1,via, end, start);
		 }
			
	 }

코드 출처 
 
위 코드와 현 문제의 코드를 작성한 지 1년간의 시간이 지났고, 저 코드를 보고 짠게 아니라 변수명이 다르다
혼선이 생길 수 있기때문에,
dstRod = end, via= tmpRod는 같은 의미임을 명시한다.
 
좀 더 자세히 설명해보자
이 문제에서는 n부터 1 디스크 원반이 원하는 막대기에 있는지만 체크하고, 없으면 위의 기존 방식처럼 만들어주면 된다.
그리고 이 문제에서는 하나하나 이동할 필요가 없고 경우의 수만 세면된다.
 
기존 하노이탑 원리를 참고해서 두가지 케이스로 나눠야 한다.
이미 재귀함수에서 놓으려고하는 현재 디스크가 원하는 막대기에 있는 경우 와 없는 경우로 나눌 수있다. 
전자는 쉽다 별도 처리없이 이미 되어있으니까. 그냥 넘어가면된다 ! (이동: 0)
후자는

• 1~ n-1 번 디스크 start->via : move(size-1,tmpRod)로 처리
• n번 디스크 start-> end:  답에 경우의 수를 더해준다.(1)
• 1~ n-1 번 디스크 via->end : 답에 경우의 수를 더해준다.(2^(n-1)-1)

막대기 번호는 1,2,3으로 했기 때문에
여기서 via를 구하는 방법은 시작점(현재 디스크가 있는 위치) 와 원하는 목적지 막대기를 6에서 빼면 남은 막대기 번호를 알 수 있다.
 
이제 경우의 수를 따지는 방법에 대해서 생각해보자.
지금 위케이스에서 후자인 경우는 1+ 2^(n-1)-1 = 2^(n-1)인 것을 알 수 있다.
여기서 매번 계산을 해도되지만, 계산의 효율을 위해 pow배열을 통해 미리 n만큼 다 계산해놓고 재귀함수를 실행시켰다.
그리고 math.pow를 사용해도 되지만 double형이므로 형변환을 해줘야한다.
2^(n) 이기 때문에 pow[i] = pow[i-1]*2 로 시간을 최소화할 수 있다.
(생략했지만, 문제 조건에 따라서 1000000으로 나눈 나머지 계산도 진행해서 수의 범위를 넘어가지 않게하는 것도 필요하다)
 
n번 디스크가 있는 막대기가 목적지 막대기이므로 이미 이동이 되어있는 상태이다.
따라서 move재귀함수를 n-1부터 실행해서 시간을 조금이라도 줄이려고 하였다...

---

작성한 코드는 다음과 같다.
move: 재귀함수(하노이탑 이동 함수)
pow: 거듭제곱 계산 배열
numRod: 막대기 별 개수가 담긴 배열
rod: 디스크 위치 배열 

import java.util.*;
import java.io.*;

public class Main {
    static int[] pow ,rod;
    static int a, b, n, k;
    static long ans = 0;

    static void move(int size, int dstRod) {
        if (size <= 0) return;
        if (dstRod == rod[size]) { // 옮길 필요가 없음
            move(size - 1, dstRod);
            return;
        }

        int tmpRod = 6 - dstRod - rod[size]; // 남은 막대기 번호 구하기
        ans += pow[size - 1]; // 이동하는 경우의 수를 더해준다.
        ans %= 1000000;
        move(size - 1, tmpRod);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(bf.readLine());
        int[] numRod = new int[3];
        pow = new int[n+1];
        rod = new int[n+1]; // rod[i]: i 번째 디스크가 속한 막대기

        st = new StringTokenizer(bf.readLine());
        for (int i = 0; i < 3; i++) {
            a = Integer.parseInt(st.nextToken());
            numRod[i] = a;
        }

        // 거듭제곱을 1000000로 나눈 나머지 배열

        pow[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow[i] = (2 * pow[i - 1]) % 1000000; // 2^n % 1000000
        }

        for (int i = 0; i < 3; i++) {
            if (numRod[i] > 0) {
                st = new StringTokenizer(bf.readLine());
                for (int j = 0; j < numRod[i]; j++) {
                    b = Integer.parseInt(st.nextToken());
                    rod[b] = i + 1; // b는 i+1 번째 막대기에 속해있다.
                    if (b == n) k = i + 1; // 마지막 번호가 속한 막대기에 디스크를 꽂는게 효율적이다.
                }
            }
        }

        move(n-1, k); 
        System.out.println(k);
        System.out.println(ans);

    }
}

 
속도 또한 빨랐다 굿 🔥

 
Eug2n2's GitHub

Algorithm/백준/Gold/2270. 하노이 탑 at main · eug2n2/Algorithm