[C] 백준 11729번 : 하노이 탑 이동 순서
오늘은 백준 11729번, 하노이 탑 문제를 풀어보았습니다 ! •̀.̫•́✧
저는 이 문제를 총 3단계에 걸쳐 해결하였습니다.
1. 어떤 방식으로 해결할지 고민하기
2. N에 1~3 정도의 숫자를 대입해서 직접 풀어보기
3. 일반화해서 코드로 작성하기
https://www.acmicpc.net/problem/11729
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5
www.acmicpc.net
1. 어떤 방식으로 해결할지 고민하기
저는 수업시간에 배웠던 DP를 활용해보았습니다.
여기서 말한 DP란 Dynamic Programming 을 뜻하는 것으로,
큰 문제를 풀기 위해 작은 문제에 대한 해답을 활용하는 알고리즘입니다.
쉽게 말하면 size가 n인 문제의 해답을 p(n)이라 할 때,
p(N)을 구하기 위해 p(N-1) 등 이전의 해를 사용하는 방식이라고 생각하면 됩니다.
.
제가 이 문제에서 DP를 사용한 이유는 우선 p(N)과 p(N-1) 사이에 연관성 이 있다고 생각했고,
주어진 N의 범위가 20 이하 라는 점에서 재귀 호출을 사용해도 괜찮겠다고 느꼈기 때문입니다.
N개의 원판을 1번 장대에서 3번 장대로 옮기려면,
우선 N-1개의 원판을 2번 장대로 옮기고
(재귀 호출을 사용할 예정이라 N-1개의 원판을 하나의 큰 덩어리로 생각합시다!)
남은 1개를 3번 장대로 옮깁니다.
그리고 N-1개의 덩어리 원판을 2번 장대에서 3번 장대로 옮기면 완성입니다.
-------------------------------------------------------------------------------------------------------------------
2. N에 1~3 정도의 숫자를 대입해서 직접 풀어보기
이렇게 1부터 3까지 손으로 직접 풀어보면서 p(N)과 p(N-1) 사이의 연관성을 찾아냅니다!
제가 찾아낸 연관성은 다음과 같습니다.
우선 N=3이라 가정하겠습니다.
(P(3)을 구해보도록 합시다!)
그럼 앞서 설명했던 그림과 같이 1번과 2번 원판(덩어리)을 1번 장대 -> 2번 장대로 이동하고
(=> 이 부분이 p(2)라는 것을 느끼셨나요?)
3번 원판은 1번 장대 -> 3번 장대로 이동합니다.
그리고 2번 장대에 있던 1번, 2번 원판을 2번 장대 -> 3번 장대로 이동시켜줍니다.
(=> 이 부분도 p(2) 입니다!)
즉 P(N)은 P(N-1) -> N번 원판을 1번 장대에서 3번 장대로 -> p(N-1)을 활용하여 구하면 됩니다!
-------------------------------------------------------------------------------------------------------------------
3. 일반화해서 코드로 작성하기
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
void hanoi(int n, int start, int middle, int end)
{
if (n == 1)
{
printf("%d %d\n", start, end);
return;
}
hanoi(n - 1, start, end, middle);
hanoi(1, start, middle, end);
hanoi(n - 1, middle, start, end);
}
int main()
{
int N;
scanf("%d", &N);
int cnt = pow(2, N) - 1;
printf("%d\n", cnt);
hanoi(N, 1, 2, 3);
return 0;
}
제가 작성한 코드입니다!
2번 과정으로 p(N)과 p(N-1)의 연관성을 찾고 나면 문제가 굉장히 쉽게 느껴지는데,
이동 과정을 출력하는 것은 조금 복잡했던 것 같습니다.
옮기는 시작점과 끝점이 계속 바뀌었기 때문입니다.
아까 p(3)을 구하는 과정을 생각해보면, 첫 번째 p(2)과 두 번째 p(2)가 다름을 알 수 있습니다.
첫번째 p(2)는 1번 장대에서 2번 장대로 이동,
두번째 p(2)는 2번 장대에서 3번 장대로 이동.
.
그래서 저는 3개의 장대를 3개의 변수로 구분을 해주었습니다.
＊ 이동을 시작하는 장대는 -> start
* 이동의 목적지 장대는 -> end
* 그 외 나머지 장대 -> middle
예를 들어 1번 장대에서 2번 장대로 원판들을 옮긴다고 하면
start = 1 , end = 2, middle = 3이 되는 것입니다.
이러한 원판의 이동 과정은 N=1이 되는 순간의 start와 end 값을 출력하면 됩니다.
(=재귀 호출을 통해 덩어리 분리 끝!)
.
+) 문제 풀면서 생긴 문제 :
처음에 저는 문제가 이동 횟수를 먼저 출력하고, 그 과정을 출력하는 것이어서
이동 내용을 별도의 배열에 저장했었습니다.
그런데 그렇게 하면 N이 큰 경우에 문제가 발생했습니다 ㅠ -> 결과가 출력이 잘 안됨,,
그래서 저는 이동 횟수 자체를 먼저 구하고 (n과 cnt의 값을 비교하면 쉽게 일반화할 수 있음!)
hanoi( ) 호출을 통해 이동 결과를 출력하였습니다.