문제
https://www.acmicpc.net/problem/11729
11729번: 하노이 탑 이동 순서
세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로
www.acmicpc.net
풀이
머리가 터질뻔 했던 문제입니다..
하노이탑을 어떻게 재귀로 구현해야할지.. 정말 막막했습니다.
유튜브에서 본 하노이탑 알고리즘이 정말 많은 도움이 되었습니다.
이해가 잘 안간다면, 한 번 보시는 것을 추천드립니다!
https://www.youtube.com/watch?v=FYCGV6F1NuY
1번 기둥(시작), 2번 기둥(보조), 3번 기둥(목표) 라고 나타내고,
hanoi(n: 기둥갯수, start: 시작기둥, to: 목표기둥, via: 보조기둥) 이라는 메서드를 정의해주었습니다.
n개의 원판을 start에서 to로 옮기는데 via 기둥을 사용하겠다 라고 간단하게 정의할 수 있습니다.
시작 기둥에 원판이 1개있다면 단순히 목표기둥으로 옮겨주면 됩니다.
시작 기둥에 원판이 2개 이상이라면,
시작 기둥에 가장 큰 원판이 남을 때 까지, 전부 보조 기둥으로 이동시켜주어야 가장 큰 원판을 목표 기둥으로 옮길 수 있습니다.
그렇다면 목표 기둥을 이용하여 시작 기둥에 있는 가장 큰 원판을 제외한 모든 원판을 보조기둥으로 옮겨주어야 합니다.
코드로는 다음과 같이 작성할 수 있습니다.
hanoi(n: n - 1, start: start, to: via, via: to)
그렇다면 전부 보조 기둥에 이동되었다면, 시작 기둥에는 1개가 남아있기 때문에 목표 기둥으로 옮겨주겠죠?
이제 보조 기둥에 있는 것들을 목표 기둥으로 옮겨주어야 하는데, 시작 기둥을 보조 기둥으로 사용하게 됩니다.
코드로는 다음과 같이 작성할 수 있습니다.
hanoi(n: n - 1, start: via, to: to, via: start)
이것을 소스코드로 옮겨주면, 하노이탑의 이동순서를 출력할 수 있습니다.
하노이탑의 이동 횟수는 $2^n - 1$ 입니다.
소스코드
후기
어려운 문제였습니다..
문제를 풀고도 이게 왜 되지? 라는 생각이 들었던 문제입니다.
DFS, 백트랙킹 문제들을 풀면서 재귀함수를 잘 사용한다고 생각했었는데.. 계속해서 연습해야겠습니다.. ㅠ
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 13241 최소공배수 (Swift) (0) | 2023.03.15 |
|---|---|
| [BOJ] 백준 1934 최소공배수 (Swift) (0) | 2023.03.15 |
| [BOJ] 백준 2447 별찍기 - 10 (Swift) (0) | 2023.03.15 |
| [BOJ] 백준 24060 알고리즘 수업 - 병합 정렬 1 (Swift) (0) | 2023.03.14 |
| [BOJ] 백준 25501 재귀의 귀재 (Swift) (0) | 2023.03.14 |
