[실버1] 11729. 하노이 탑 이동 순서 (Java)

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

11729번: 하노이 탑 이동 순서

 SSAFY 동기 분들 다들 괴물입니다,,,

---

※  문제를 요약하면 아래와 같습니다.

▶ 세 곳의  막대를 쌓을 수 있는 공간이 존재 (왼쪽, 가운데, 오른쪽)

▶ 첫 번째 공간에 값이 밑에서 부터 큰 순서 대로 쌓여 있음

▶ 모든 공간에서 작은 막대는 큰 막대 밑에 존재할 수 없음

▶ 위의 조건을 유지한 채,  최소한의 횟수로 가장 오른쪽 공간에 처음과 동일한 형태가 될 수 있도록 옮김

▶ 입력은 가장 왼쪽 공간에 쌓일 막대의 갯수

▶ 출력은 막대를 움직인 최소 횟수와 이동 경로 출력

---

◈ Input

3

◈ Output

7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

 

 

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 재귀 함수 설계로 문제 풀이

▶ 재귀 함수의 매개 변수를 ( 현재 막대의 갯수 , 출발 위치, 매개 위치, 목표 위치)로 설계  

     ( 여기서의 매개 위치란 출발 위치에서 목표위치로 이동하기 위한 매개 위치입니다!)

▶ 재귀 함수의 재귀 부분을 크게 세가지로 설계

    1. 제일 큰 숫자가 스타트 위치에 하나 남고, 나머지 블럭들이 모두 매개 위치에 위치

    2. 제일 큰 숫자를 출발 위치에서 목표 위치로 이동

    3. 매개 위치의 모든 블럭을 목표 위치로 이동 

    4. 막대의 갯수를 하나씩 깎으며 재귀, 막대가 1개만 존재할 경우 이동 경로 출력

▶ 예시 - 1.  입력이 4 ( 가장 왼쪽 위치가 4 , 코드와 비교하면서 확인해 보세요!) 

    - 막대 4개 시작위치 1, 매개위치2, 목표위치 3의 값을 가지고 시작

 

    - 가장 위에 있는 (3,1,3,2)가 재귀되는 형태만 그림으로 표시

        ( 4만 가장 오른쪽에 위치,  1,2,3 은 두번 째 위치에 배치되는 과정 )

  (4,1,2,3) 

  (1,1,3,2)   -> 1번째 위치의 가장 높은 블럭 하나가 2번째 위치로 이동

  (1,1,2,3)   -> 1번째 위치의 가장 높은 블럭 하나가 3번째 위치로 이동

  (1,2,1,3)   -> 2번째 위치의 가장 높은 블럭 하나가 3번째 위치로 이동

  (1,1,3,2)   -> 1번째 위치의 가장 높은 블럭 하나가 2번째 위치로 이동

  (1,3,2,1)   -> 3번째 위치의 가장 높은 블럭 하나가 1번째 위치로 이동

   (1,3,1,2)   -> 3번째 위치의 가장 높은 블럭 하나가 2번째 위치로 이동

    (1,1,3,2)   -> 1번째 위치의 가장 높은 블럭 하나가 2번째 위치로 이동

    (1,1,2,3)   -> 1번째 위치의 가장 높은 블럭 하나가 3번째 위치로 이동

이후로는 직접 코드 구현해보시거나 아래의 코드를 참조하여 따라가 보시면 좋을 것 같습니다!

---

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

public class Main {
	static BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));
	static int nMove = 0;
	
	public static void Hanoi(int nSize, int nFrom, int nTo, int nEnd) throws IOException {
		// 이동 보여주기
		if(nSize == 1) {
			nMove++;
			bWriter.write(nFrom + " " + nEnd + "\n");
			return;
		}
		
		// 제일 큰 숫자가 스타트 위치에 하나가 남을 때 까지 무브
		Hanoi(nSize-1, nFrom, nEnd, nTo);
		
		// 제일 큰 숫자를 From->End로 이동
		Hanoi(1, nFrom, nTo, nEnd);
		
		// 제일 큰 숫자를 제외한 나머지 탑들을 end위치로 이동
		Hanoi(nSize-1, nTo, nFrom, nEnd);
	}

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));

		int nHanoiSize = Integer.parseInt(bReader.readLine());
		
		// 최소 이동 개수 : 2^n -1
		int nMovebyFormula = (int)Math.pow(2, nHanoiSize) - 1;
		bWriter.write(nMovebyFormula + "\n");
		Hanoi(nHanoiSize, 1, 2, 3);
		//bWriter.write("내가 한 거 : " + nMove + "\n");
		
		bWriter.flush();
		bWriter.close();

	}

}

 알고리즘 스터디 동기분의 힌트를 받아 하노이의 탑을 이해 할 수 있었습니다!! 모르고리즘 화이팅!

읽어주셔서 감사합니다!

Good Luck! (피드백 감사합니다!)