11729 하노이 탑 이동 순서 : https://www.acmicpc.net/problem/11729
Problem
Solve
재귀함수를 이용한 문제입니다.
1에서 N순으로 판을 옮겨야 하는것에 초점을 맞춰서 접근하였는데 해결이되지 않아 다른 분의 풀이에서 N부터 접근해야한다는 힌트를 얻었습니다.
옮겨야할 판이 있는 위치 : left
판이 이동해야할 위치 : right
나머지 위치 : mid
로 먼저 정의하겠습니다.
가장 아래있는 원판(N)이 이동해야할 위치는 3입니다.
즉, N의 위치 정보는 left = 1, mid = 2, right = 3이 되게 됩니다.
그렇다면 N원판 위에있는 판(N-1)을 이동시킬 경우, N원판이 이동한 위치가 아닌 나머지 위치(2)로 이동을 시켜야합니다.
즉, N-1의 위치 정보는 left = 1, mid = 3, right = 2가 되게 됩니다.
정리해보자면, 원판을 이동시킬때 이전 원판이 출발한 위치는 동일하고 도착할 위치는 이전 원판이 이동하지 않은 나머지 위치로 이동해야합니다.
이전 원판의 위치 정보가 left = 1, mid = 2, right = 3이라면 다음 원판의 위치 정보는 left = 1, mid = 3, right = 2이 되어야하므로
hanoi(block-1, left, right, mid)로 재귀를 호출할수 있게됩니다.
그럼 반대로 원판을 이동시켰다면 이전 원판의 위로 이동시켜줘야합니다.
원판은 현재 위치에서 이전 원판이 이동한 위치로 이동해줘야합니다.
이전 원판의 위치정보가 left = 1, mid = 2, right = 3 일때, 다음 원판은 나머지 위치에서 원판의 도착 위치로 이동시켜야합니다.
즉, left = 2, mid = 1, right = 3이 되어야합니다.
이를 hanoi(block-1, mid, left, right)로 재귀를 호출할수 있게됩니다.
hanoi(int block, int left, int mid, int right){
//원판이 0이될때까지 원판을 이동시켜줘야합니다.
if(block == 0) return;
//이전 원판이 이동하지 않은 위치로 이동시켜줘야합니다.
//다음 원판의 출발지점은 현재 원판 위치와 동일합니다(left==1), 도착지점은 현재 원판이 이동하지 않을 위치(mid)
hanoi(block-1, left, right, mid);
//현재 원판 출발지점(left)에서 도착지점(right)
sb.append(left).append(" ").append(right);
//이동시켰던 원판을 현재 원판 위에 위치시키도록 이동시켜줘야합니다.
//다음 원판의 출발지점은 현재 원판이 이동하지 않은 위치(mid), 도착지점은 현재 원판이 이동할 위치(right)
hanoi(block-1, mid, left, right);
}Code
import java.io.*;
public class Main{
static StringBuilder sb;
static int count;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int N = Integer.parseInt(br.readLine());
sb = new StringBuilder();
count = 0;
hanoi(N,1,2,3);
StringBuilder result = new StringBuilder();
result.append(count).append("\n");
result.append(sb);
bw.write(result.toString());
bw.flush();
bw.close();
}
static void hanoi(int block, int left, int mid, int right){
if(block == 0) return;
count++;
hanoi(block-1, left, right, mid);
sb.append(left).append(" ").append(right).append("\n");
hanoi(block-1, mid, left, right);
}
}Result
Reference
