백준 11729번: 하노이 탑 이동 순서 [분할정복][재귀] - Java

www.acmicpc.net/problem/11729

11729번: 하노이 탑 이동 순서

재귀함수의 대표문제인 "하노이의 탑" 을 이제 풀어봤다.

사실 아예 로직을 몰라서 처음에는 홀수면 3번째탑.. 짝수면 2번째 탑으로간다음.. 위에 큰게있으면 안되고.. 이런식으로  if문들의 범벅을 생각하다가 간단한 풀이을 보고 충격을 먹었다.. 재귀함수를 자유자재로 쓰는 능력이 아직 많이 부족한듯하다.

 

shoark7.github.io/programming/algorithm/tower-of-hanoi

'하노이의 탑' 이해하기

하노이의 탑 로직에 아주 이해가 많이 되었던 분의 블로그. 까먹으면 다시가서 보고 와야징

 

 

<풀이 방법>

1. n>1인 n번 원판을 최종 목적지에 옮기기 위해서는 자신이 속한 기둥에 자기 위에 아무 원판도 없어야한다.

그렇기에 n-1원판을 경유지로 옮겨준다.

(여기서 재귀발생.. n-1원판은 또 자길 옮기기 위해선 n-2원판을 경유지로 옮기겠지.. 그럼 n-2원판은 또 n-3원판을 옮기고.....)

 

2. n번 원판을 원하는 최종 목적지에 옮긴다 (cnt++)

 

3. 그리고 경유지에 옮겨놓았던 n-1,n-2,n-3.....1번의 원판을 다시 n번 원판위로 올려준다.

(여기서도 재귀발생 아까 이동한것 처럼 n-1을 n번 원판이 있는 기둥으로 옮기기 위해선 n-2부터 옮겨야한다.) 

 

4. n==1이면 자기 바로 위의 원판이 절대 있을수 없을 것이니 그냥 자기만 바로 슉 옮기면된다.

 

 

 

- Scanner와 ArrayList를 통해 sysout을 해서 시간초과가 난 코드

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static int cnt=0;
	public static ArrayList<String> arr = new ArrayList<>();
	public static void main(String[] args)  {

		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		
		//시작
		hanoi(N,1,3,2); //1번 기둥에 있는 N개의 원판을 2번 기둥을 경유하여 최종 목적지인 3번으로 옮겨야한다.
		
		System.out.println(cnt);
		for(String str : arr) {
			System.out.println(str);
		}
	}
	
	public static void hanoi(int n, int start, int end, int via) {
		
		if(n==1) {
			cnt++; //옮길때마다 카운트 ++
			arr.add(start+" "+end);
		}
		else {
			hanoi(n-1,start,via,end); //n번 원판을 최종 목적지로 옮기기 위해서 그 위에있는 n-1원판을 다른곳(via)으로 옮겨 놓는다.
			arr.add(start+" "+end); // n-1원판이 다른곳으로 옮겨졌으면 n번 원판을 최종 목적지로 이동시킨다.
			cnt++;					// 원판을 옮길때마다 카운트 ++
			hanoi(n-1,via,end,start); //다른곳(via)에 옮겨놨던 n-1원판을 다시 n번의 위로 옮겨준다.
		}
		
	}

}

 

- BufferedReader와 StringBuilder를 통하여 출력했더니 성공

이 기회에... 두개 사용법을 좀 익혀둬야겠다. 오랜만에 쓰려니 new 방법부터 헷갈렸당

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

public class Main {

	public static int cnt=0;
	public static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		
		//시작
		hanoi(N,1,3,2); //1번 기둥에 있는 N개의 원판을 2번 기둥을 경유하여 최종 목적지인 3번으로 옮겨야한다.
		
		System.out.println(cnt);
		System.out.println(sb);
		
		
	}
	
	public static void hanoi(int n, int start, int end, int via) {
		
		if(n==1) {
			cnt++; //옮길때마다 카운트 ++
			sb.append(start+" "+end+"\n");
		}
		else {
			hanoi(n-1,start,via,end); //n번 원판을 최종 목적지로 옮기기 위해서 그 위에있는 n-1원판을 다른곳(via)으로 옮겨 놓는다.
			sb.append(start+" "+end+"\n"); // n-1원판이 다른곳으로 옮겨졌으면 n번 원판을 최종 목적지로 이동시킨다.
			cnt++;					// 원판을 옮길때마다 카운트 ++
			hanoi(n-1,via,end,start); //다른곳(via)에 옮겨놨던 n-1원판을 다시 n번의 위로 옮겨준다.
		}
		
	}

}

 

 

기억하자