백준 알고리즘 1914번: 하노이 탑 [C++]

문제 출처: www.acmicpc.net/problem/1914

1914번: 하노이 탑

 

1. 코드

 

 

(실행)

 

2. 풀이

우선 하노이 탑에 대한 알고리즘에 대해 설명하겠다. 하노이 탑의 알고리즘은 재귀 함수를 이용하여 풀었는데 재귀 함수에 대해 너무 어렵게 접근할 필요가 없고, 실행 순서에 대해 정확히 알려고 하지 않아도 된다. 본질에 집중해야 한다. 우선 하노이 탑이 움직이게 되는 조건들을 살펴보자.

참고 그림 - 1

참고 그림 - 2

참고 그림 - 3

참고 그림 - 4

그림 - 4에서 7단계를 보면 제일 마지막 원판이 남았을 때는 기둥 1에서 기둥 3으로 이동하기에 다음과 같이 코드가 나온다.

if (num == 1) printf("%d %d\n", from, to);

그리고 만약 아닐 경우에는 다른 작업을 이어 나아가야 한다. 그렇다면 반복 패턴을 살펴보자. 그림 - 2에서 3단계를 보면 2개의 원판이 기둥 2로 모인다. 그것을 코드로 나타내면 다음과 같다.

HanoiTower(num - 1, from, to, by);

그리고 기둥 1에 있는 큰 원판을 기둥 3으로 움직여야 한다. 그것을 코드로 나타내면 다음과 같다.

printf("%d %d \n", from, to);

마지막으로 기둥 2에 있는 원판들을 기둥 3으로 움직이면 된다. 그것을 코드로 나타내면 다음과 같다.

HanoiTower(num - 1, by, from, to);

이렇게 해서 하노이 탑에 대한 알고리즘은 해결할 수 있다. 그런데 이제 새로운 문제가 생긴다. 예제 출력에서 첫 번째 출력이 원판 이동 횟수를 출력해야 하는데 원판 이동 횟수에 대한 공식은 다음과 같다.

 하노이 탑에 대한 원판 이동 횟수 = 2^x - 1

그런데 20이 넘어가면 자료형 int로 표현할 수 없다. 그렇기 때문에 문자열을 이용하여 이 문제를 해결하였다. 우선 2의 N 제곱을 문자열로 만들었다.

string a = to_string(pow(2, N));

여기서 pow는 제곱을 시켜주는 함수이다. 그런데 pow 함수는 double 형이기에 실수가 저장이 된다. 그러면 문자로 변환을 했지만 실수형이기에 소수 점이 저장된다. 그래서 .find를 이용하여 소수 점을 찾는다.

int x = a.find('.');

그러면 소수 점의 위치가 반환되는데 .substr을 이용하여 소수 점 앞자리만 저장되게 한다.

a = a.substr(0, x);

그리고 공식은 2^x -1이기에 문자열의 마지막 인덱스 값에 접근하여 그 값에 -1을 해준다.

a[a.length() - 1] -= 1;

그리고 문제에서 20 이상의 경우에는 원판 이동 과정을 보여주지 않아도 되기에 20 이하만 이동 과정을 보여줄 수 있게 하면 끝이다.

if(N <= 20)
	HanoiTower(N, 1, 2, 3);

 

3. 느낀 점

재귀에 대해 너무 실행 과정에 얽매이지 않고 조금 더 본질에 집중하도록 노력해야겠다.