11729 - 하노이탑 이동 순서

0. 개요

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

11729번: 하노이 탑 이동 순서

재귀 문제 중에서 가장 이해가 안되었던 문제였습니다.

코드를 봐도 이해가 안갔던 문제인데 오늘 접근방법이 떠올랐고 문제를 드디어 해결했습니다.

저와 같이 코드를 봤어도 이해가 안갔던 분들을 위하여 상세하게 풀이 과정을 서술해보겠습니다.

 

 

1. 풀이과정

문제에서 제시하는 바는 위와 같습니다.

1번 기둥에 있는 원판을 모두 3번으로 이동 시키는 것입니다.

하노이의 탑 문제의 규칙은 모두 알고 있다고 가정을 하겠습니다.

 

 

1-1. 이동할 방향 선정?

(아래는 도출 과정입니다. 답을 원하시는 분은 1-2로 바로 넘어가 주세요.)

제가 맨처음 접근한 방식은 다음과 같습니다.

맨위의 녀석을 2번과 3번 둘중 하나에 선택하여 이동하고 그다음 원판을 같이 이동, 이동,.. 하여 맨 밑에까지,

맨위의 작은 원판부터 접근을 했습니다.

 

그러자 하나의 문제점에 도달했습니다.

원판의 갯수에 따라 제일 작은 원판이 2번에 가야 할 수도, 3번에 가야 할 수도 있는 상황이 되었습니다.

조건이 많아지는 것은 매우 귀찮아지는 일입니다.

또한 알고리즘은 똑같은 동작 원리에 의하여 이동하는 것이 일반적으로 편하겠죠.

 

그렇다면 어떻게 해야할까요?

여기서 떠올린 점이 다음과 같습니다.

 

1-2. 맨 아래서 부터 선택하여 올라가자.

가장 큰 원판을 3번으로 이동시켜 놓는다면 모든 일이 해결됩니다.

 

가장 큰 선반을 3번으로 옮긴다고 가정했을 때, 위의 나머지 4개를 옆으로 치워줘야 3번으로 이동 할 수 있겠죠.

 

그렇다면 파란색 구간을 옮기기 위해서는 파란색 구간의 가장 넓은 원판을 치워야합니다.

 

이제 감이 좀 오시는가요?

 

파란색 구간을 치우기 위해서는 녹색 구간을 치워야하고..

녹색 구간을 치우기 위해서는 노란색 구간을 치워야하고..

 

여기서 재귀적 특징이 나타납니다.

 

그럼 치우는 것 까지는 알겠습니다.

 

그렇다면 어디로 치워줘야 할까요?

위의 그림을 살펴보면 알 수 있습니다.

편의상 가장 큰 원판을 5부터 가장 작은 원판을 1이라 하겠습니다.

 

먼저 우리의 목표는 1번에 있는 5번 원판을 3번으로 이동시키는 것입니다.(빨간색 화살표)

그렇게 하기 위해서는 1~4번까지의 윗부분이 자리를 비켜줘야 합니다.

 

파란색 부분은 2번밖에 비켜줄 자리가 없는 것을 확인할 수 있습니다.

 

다만 4개의 원판을 한번에 움직이는 것은 불가능하죠.

재귀의 원리에 의해서 맨 꼭대기 부터 이동해줘야 합니다.

다만 빨간색이 3번으로 가야하기 때문에 빨간색을 3번으로 먼저 보내고,

4-3-2-1 순서로 2번과 3번을 교차해서 보내주면 위와 같이 됩니다.

 

즉, 우리가 처음 할 일은 먼저 각 원판이 어디로 자리를 비켜줄지를 먼저 정하는겁니다.

 

 

먼저 위와 같이 1번에 있는 4개의 원판이 자리를 비켜줬다고 생각해봅시다.

그러면 가장큰 5번 원반을 3번으로 이동하기만 하면 되겠죠.

 

 

그 다음 상황은 다음과 같습니다.

5번 원판은 3번으로 이동했습니다.

그럼 나머지 원판을 3번으로 이동시켜 줘야겠죠.

 

이것 또한 위와 같이 각각 이동할 수 있는 위치를 살펴보고 빈 자리 에다 이동해줍니다.

 

여기서 빈자리는 어떻게 찾을것인가에 대한 논의가 필요합니다!!

 

1번 2번 3번 세개의 위가 있습니다.

 

1+2+3을 한다면 6이라는 값이 나오겠죠?

 

만약 지금 2 -> 3으로 갔다고 생각한다면, 1번이 비어있습니다.

 

이는 다음과 같은 식으로 구할 수 있습니다.

 

6 - (2 + 3) = 1

 

즉, 6에서 현재 위치와 도착 지점을 더한 값을 뺀다면 다음에는 어디로 보내야 할지 알 수 있습니다.

 

위의 예제로 생각한다면,

주황색은 3번으로 갔습니다. 2->3입니다.

 

그렇다면 다음에 가야할 위치는 6-(2+3) = 1 번째 라고 알 수 있습니다.

 

나머지 부분에 대해서도  동일하게 적용하면 됩니다.

 

 

그렇다면 아래와 같이 이동하게 되고 끝나겠죠.

 

2. 소스코드

 

#include<iostream>

using namespace std;

int cnt = 0;

/* ans() 함수는 hanoi() 함수에서 출력만 제거한 함수입니다. */
/* 문제에는 총 이동 횟수를 먼저 출력한 뒤 이동한 위치를 출력하도록 되어 있어 이동 횟수를 먼저 구하는 함수입니다 */
/* 내부적인 설명은 아래 hanoi() 함수에 적도록 하겠습니다. */

void ans(int s, int e, int n) {
	if (n == 1) {
		cnt++;
		return;
	}
	int next = 6 - (s + e);
	ans(s, next, n - 1);
	cnt++;
	ans(next, e, n - 1);
}

/* 시작과 끝, 현재 몇번째 원판을 빼야하는지에 대한 값을 매개변수로 받아옵니다. */
void hanoi(int s, int e, int n) {
	if (n == 1) {
        /* 만약 빼야하는 원판이 1, 즉 제일 작을 때는 다른걸 굳이 안옮기고 바로 옮길 수 있습니다 */
		cout << s << " " << e<<"\n";
		return;
	}
    
    /* 6에서 시작+끝 값을 빼줌으로써 다음 위치를 구합니다. */
	int next = 6 - (s + e);
    
    /* 현재의 가장 큰 원판을 옮기기 위하여 그 위의 것들을 이동시켜 줍니다. */
	hanoi(s, next, n - 1);
    
    /* 가장 큰 원판을 이동 시킵니다 */
	cout << s << " " << e<<"\n";
    
    /* 가장 큰 원판을 이동시키기 위하여 비켜준 친구들을 다시 가장큰 원판 위로 옮깁니다 */
	hanoi(next, e, n - 1);
}

int main(void) {
	int N;

	cin >> N;
	
    /* ans를 통하여 cnt 값을 구하고 출력 후 hanoi() 함수를 실행시켜 이동 경로를 출력합니다. */
	ans(1, 3, N);
	cout << cnt << "\n";
	hanoi(1, 3, N);
}

 

제가 가장 어려웠던 것은

hanoi(s, next, n-1);

cout<<s<<" '<<e"\n";

hanoi(next, e, n-1); //이부분

이었습니다.

 

이부분은 아래와 같이 비켜준 원판들을 가장 큰 원판이 이동한 위치로 옮겨준다고 생각하시면 됩니다.

위가 이부분에 해당하는 코드이고, 

hanoi(s, next, n-1);

cout<<s<<" '<<e"\n";

 

위가 이부분에 해당하는 코드라고 보시면 됩니다.

hanoi(next, e, n-1);