ํ๋
ธ์ด ํ(Tower of Hanoi)
์ ํผ์ฆ์ ์ผ์ข
์
๋๋ค. ์ธ ๊ฐ์ ๊ธฐ๋ฅ๊ณผ ์ด ๊ธฐ๋์ ๊ฝ์ ์ ์๋ ํฌ๊ธฐ๊ฐ ๋ค์ํ ์ํ๋ค์ด ์๊ณ , ํผ์ฆ์ ์์ํ๊ธฐ ์ ์๋ ํ ๊ธฐ๋ฅ์ ์ํ๋ค์ด ์์ ๊ฒ์ด ์์ ์๋๋ก ์์๋๋ก ์์ฌ ์์ต๋๋ค. ๊ฒ์์ ๋ชฉ์ ์ ๋ค์ ๋ ๊ฐ์ง ์กฐ๊ฑด์ ๋ง์กฑ์ํค๋ฉด์, ํ ๊ธฐ๋ฅ์ ๊ฝํ ์ํ๋ค์ ๊ทธ ์์ ๊ทธ๋๋ก ๋ค๋ฅธ ๊ธฐ๋ฅ์ผ๋ก ์ฎ๊ฒจ์ ๋ค์ ์๋ ๊ฒ์
๋๋ค.
- ํ ๋ฒ์ ํ๋์ ์ํ๋ง ์ฎ๊ธธ ์ ์์ต๋๋ค.
- ํฐ ์ํ์ด ์์ ์ํ ์์ ์์ด์๋ ์๋ฉ๋๋ค.
ํ๋
ธ์ด ํ์ ์ธ ๊ฐ์ ๊ธฐ๋ฅ์ ์ผ์ชฝ ๋ถํฐ 1๋ฒ, 2๋ฒ, 3๋ฒ์ด๋ผ๊ณ ํ๊ฒ ์ต๋๋ค. 1๋ฒ์๋ n
๊ฐ์ ์ํ์ด ์๊ณ ์ด n
๊ฐ์ ์ํ์ 3๋ฒ ์ํ์ผ๋ก ์ต์ ํ์๋ก ์ฎ๊ธฐ๋ ค๊ณ ํฉ๋๋ค.
1๋ฒ ๊ธฐ๋ฅ์ ์๋ ์ํ์ ๊ฐ์ n
์ด ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, n
๊ฐ์ ์ํ์ 3๋ฒ ์ํ์ผ๋ก ์ต์๋ก ์ฎ๊ธฐ๋ ๋ฐฉ๋ฒ์ returnํ๋ solution
๋ฅผ ์์ฑํด์ฃผ์ธ์.
n
์ 15์ดํ์ ์์ฐ์ ์
๋๋ค.n | result |
---|---|
2 | [ [1,2], [1,3], [2,3] ] |
๋ค์๊ณผ ๊ฐ์ด ์ฎ๊ธธ ์ ์์ต๋๋ค.
ํ๋
ธ์ด์ ํ ๋ฌธ์ ๋ ๊ท์น์ด ์กด์ฌํ๋ ๋ํ์ ์ธ ์ฌ๊ท ๋ฌธ์ ์ด๋ค.
๊ทธ๋ ๊ธฐ ๋๋ฌธ์, ์ ํ์์ ์ธ์ฐ๋ฉด ์ฝ๊ฒ ๊ตฌํํ ์ ์๋ค.
์ฐ์ ์ถ๋ฐ์ง, ๊ฒฝ์ ์ง, ๋์ฐฉ์ง ์ด๋ ๊ฒ 3๊ฐ์ ์์น๋ฅผ ์ ์ธํ๋ค.
๊ทธ๋ฆฌ๊ณ ์ฐ๋ฆฌ์ ์ต์ข
๋ชฉํ์ธ n
๊ฐ์ ์ํ์ ์ถ๋ฐ์ง์์ ๋์ฐฉ์ง๋ก ์ฎ๊ธฐ๋ ๊ณผ์ ์์ ์๋์ ๊ท์น์ด ๋ฐ์ํ๋ค.
n-1๊ฐ, ์ถ๋ฐ์ง -> ๊ฒฝ์ ์ง
+1๊ฐ, ์ถ๋ฐ์ง -> ๋์ฐฉ์ง
+n-1๊ฐ, ๊ฒฝ์ ์ง -> ๋์ฐฉ์ง
๊ทธ๋ฆฌ๊ณ ์ด๋ฅผ ์ฝ๋๋ก ๊ตฌํํด๋ณด์!
import java.util.*;
class Solution {
private static List<int[]> arr = new ArrayList<>();
public int[][] solution(int n) {
move(n, 1, 2, 3);
int[][] answer = arr.stream()
.toArray(int[][]::new);
return answer;
}
private static void move(int cnt, int start, int mid, int end) {
if (cnt == 0) {
return;
}
move(cnt - 1, start, end, mid);
arr.add(new int[]{start, end});
move(cnt - 1, mid, start, end);
}
}
์ฐ์ , ์ด๋ ์ ๋ณด๋ฅผ ์ ์ฅํ ๋ณ์ List<int[]> arr
๋ฅผ ์ ์ธํด ์ฃผ์๋ค.
๊ทธ๋ฆฌ๊ณ , ์ํ์ ์ฎ๊ธฐ๋ ๋ฉ์๋ move
๋ฅผ ๋ง๋ค์ด ์ฃผ์๋๋ฐ, ์ฌ๊ธฐ์ cnt
๋ ์ด๋ํ ์ํ์ ๊ฐ์์ด๊ณ , start
๋ ์ถ๋ฐ์ง, mid
๋ ๊ฒฝ์ ์ง, end
๋ ๋์ฐฉ์ง์ด๋ค.
move(cnt - 1, start, end, mid);
arr.add(new int[]{start, end});
move(cnt - 1, mid, start, end);
๋ง์ง๋ง์ผ๋ก ์์ ์ฐพ์ ๊ท์น์ ๋ฐํ์ผ๋ก ์ ํ์์ ์์ฑํด ์ฃผ๋ฉด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ ์ ์๋ค.