(C++) 백준 11729번 [하노이 탑 이동 순서]

안녕하세요 평범한 컴공생입니다.

 

백준 11729번 [하노이 탑 이동 순서] 문제 알고리즘 포스팅을 해보겠습니다.

사실 학교에서 전공 공부를 하면서 하노이 탑 이동 순서와 관련한 문제를 접한 적이 있었는데 그때는 그냥 혼자 해결하기 위해 고민하는 시간 없이 구글링으로 과제를 했던 기억이 나 이번엔 반드시 내 힘으로 풀겠다!는 마음가짐으로 문제를 풀었습니다..!

전형적인 재귀함수입니다. 재귀함수를 사용하려면 어떠한 함수가 다음 항의 함수값에 영향을 주는 규칙적인 형태를 띌 때 사용하기에 적절합니다. 하노이 탑이 그러합니다.

실버 2 난이도의 문제입니다.

1. 문제 해결 방법 구상하기

 - 하노이 탑이 1층이면 그냥 그거 하나만 3번 기둥으로 옮기면 된다. >> 2층이면? 위의 원판을 2번째로 옮기고, 밑의 원판을 3번 기둥으로 옮긴 후 2번째 기둥으로 옮겨놨던 원판을 3번으로 옮긴다. >> 3층이라면? 위의 두 원판을 2번째 기둥으로 옮겨놓고 젤 밑의 원판을 3번째 기둥으로 옮겨놓은 후 2번째 기둥으로 옮겨놓은 원판을 3번째 기둥으로 옮긴다. 이때, 젤 밑에있던 기둥이 제일 크므로 3번째 기둥으로 옮긴 후에 다른 원판의 움직임에 아무런 관여를 하지 않는다.

 ===> 그렇다면 개수가 N일 때, 1층의 원판 위의 원판들을 2번째 기둥으로 옮겨놓고, 1층의 원판을 3번째 기둥으로 옮기고 다시 2번째 기둥에 옮겨놨던 원판들을 3번째 기둥으로 옮기면 된다. 즉! N-1개일 때의 이동을 3번째 기둥으로 할 것이냐 2번째 기둥으로 할 것이냐의 차이일 뿐이다.

 

2. 구상한 아이디어를 바탕으로 코딩하기

#include <iostream>
#include <cmath>

using namespace std;

void move(int from, int to) // 제일 밑의 원판을 3번 기둥으로 옮기는 작업(함수)
{
	cout << from << " " << to << endl;
}

void Hanoi(int N, int start, int temp, int dest)
{
	if (N == 1)
		move(start, dest);
	else if (N > 1)
	{
		Hanoi(N - 1, start, dest, temp); // 기둥의 목적지가 temp 에서 dest로 dest에서 temp로
        								 // 바뀐 것 뿐이다!
		move(start, dest);
		Hanoi(N - 1, temp, start, dest); // temp 에 있던 원판들이므로 temp 에서 start를 거쳐
        								 // dest로 옮기는 것이다!
	}
}

int main()
{
	int N;
	cin >> N;
	cout << (1 << N) - 1 << endl;
	Hanoi(N, 1, 2, 3);

	return 0;
}

이렇게 풀고 컴파일 후 입력을 받았는데 아무 문제없이 출력값이 나오길래 백준사이트에 제출을 했는데..!

어이없게도 계속 시간 초과가 떴다. 무슨 이런 이상한 문제가 있나해서 여러 방법을 시도해보았지만 계속해서 시간 초과만 반복될 뿐이었다. 그러다가 c++에서의 cin과 cout 그리고 endl이 c언어에서의 scanf, printf 그리고 개행(\n)과 차이점이 있다는 사실을 어디선가 얼핏 들었던 기억이 나 endl 을 개행으로 바꿔주었더니..

정답이라고 인정받았다..

c언어에서의 scanf, printf 그리고 개행(\n)이 c++에서의 그것들보다 수행속도에서 더 빠르다는 것을 구글링을 통해 알게되었고 아직 버퍼의 개념과 라이브러리에서의 함수들을 정확히 알지 못해 왜 수행속도에서 차이가 나는지 정확히는 알 수 없지만 앞으로 시간 단축을 위해 scanf와 printf, 개행을 c++ 에서도 활용해야겠다는 교훈을 얻었던 문제였다.

 

// 문제제기 및 피드백 언제든지 감사히 받겠습니다.