[C] 백준 11729번 : 하노이 탑 이동 순서

오늘은 백준 11729번, 하노이 탑 문제를 풀어보았습니다 !  •̀.̫•́✧ 

저는 이 문제를 총 3단계에 걸쳐 해결하였습니다.

1. 어떤 방식으로 해결할지 고민하기

2. N에 1~3 정도의 숫자를 대입해서 직접 풀어보기

3. 일반화해서 코드로 작성하기

 

백준 11729번

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

11729번: 하노이 탑 이동 순서

 

1. 어떤 방식으로 해결할지 고민하기

저는 수업시간에 배웠던 DP를 활용해보았습니다.

여기서 말한 DP란 Dynamic Programming 을 뜻하는 것으로,

큰 문제를 풀기 위해 작은 문제에 대한 해답을 활용하는 알고리즘입니다.

쉽게 말하면 size가 n인 문제의 해답을 p(n)이라 할 때,

p(N)을 구하기 위해 p(N-1) 등 이전의 해를 사용하는 방식이라고 생각하면 됩니다.

.

제가 이 문제에서 DP를 사용한 이유는 우선 p(N)과 p(N-1) 사이에 연관성 이 있다고 생각했고,

주어진 N의 범위가 20 이하 라는 점에서 재귀 호출을 사용해도 괜찮겠다고 느꼈기 때문입니다.

 

0123

옆으로 넘겨서 보세용

 

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( ) 호출을 통해 이동 결과를 출력하였습니다.