Chapter5. ์ฌ๊ท
[๋ฌธ์ 17] ํ๋
ธ์ด์ ํ - Level3
ํ๋
ธ์ด ํ์ ํผ์ฆ์ ์ผ์ข
์
๋๋ค. ์ธ ๊ฐ์ ๊ธฐ๋ฅ๊ณผ ์ด ๊ธฐ๋ฅ์ ๊ฝ์ ์ ์๋ ํฌ๊ธฐ๊ฐ ๋ค์ํ ์ํ๋ค์ด ์๊ณ , ํผ์ฆ์ ์์ํ๊ธฐ ์ ์๋ ํ ๊ธฐ๋ฅ์ ์ํ๋ค์ด ์์ ๊ฒ์ด ์์ ์๋๋ก ์์๋๋ก ์์ฌ ์์ต๋๋ค. ๊ฒ์์ ๋ชฉ์ ์ ๋ค์ ๋ ๊ฐ์ง ์กฐ๊ฑด์ ๋ง์กฑ์ํค๋ฉด์, ํ ๊ธฐ๋ฅ์ ๊ฝํ ์ํ๋ค์ ๊ทธ ์์ ๊ทธ๋๋ก ๋ค๋ฅธ ๊ธฐ๋ฅ์ผ๋ก ์ฎ๊ฒจ์ ๋ค์ ์๋ ๊ฒ์
๋๋ค.
- ํ ๋ฒ์ ํ๋์ ์ํ๋ง ์ฎ๊ธธ ์ ์์ต๋๋ค.
- ํฐ ์ํ์ด ์์ ์ํ ์์ ์์ด์๋ ์ ๋ฉ๋๋ค.
ํ๋
ธ์ด ํ์ ์ธ ๊ฐ์ ๊ธฐ๋ฅ์ ์ผ์ชฝ๋ถํฐ 1๋ฒ, 2๋ฒ, 3๋ฒ์ด๋ผ๊ณ ํ๋ฉด 1๋ฒ์๋ n๊ฐ์ ์ํ์ด ์๊ณ ์ด n๊ฐ์ ์ํ์ 3๋ฒ ์ํ์ผ๋ก ์ต์ ํ์๋ก ์ฎ๊ธฐ๋ ค๊ณ ํ๋ค.
1๋ฒ ๊ธฐ๋ฅ์ ์๋ ์ํ์ ๊ฐ์ n์ด ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, n๊ฐ์ ์ํ์ 3๋ฒ ์ํ์ผ๋ก ์ต์๋ก ์ฎ๊ธฐ๋ ๋ฐฉ๋ฒ์ returnํ๋ solution๋ฅผ ์์ฑํด์ฃผ์ธ์.
- n์ 15์ดํ์ ์์ฐ์์
๋๋ค.
- 1๋ฒ ์ํ์ 3๋ฒ ํ์ผ๋ก ์ด๋
- 2๋ฒ ์ํ์ 2๋ฒ ํ์ผ๋ก ์ด๋
- 1๋ฒ ์ํ์ 2๋ฒ ํ์ผ๋ก ์ด๋
- 3๋ฒ ์ํ์ 3๋ฒ ํ์ผ๋ก ์ด๋
- 1๋ฒ ์ํ์ 1๋ฒ ํ์ผ๋ก ์ด๋
- 2๋ฒ ์ํ์ 3๋ฒ ํ์ผ๋ก ์ด๋
- 1๋ฒ ์ํ์ 3๋ฒ ํ์ผ๋ก ์ด๋
//๊ณผ์ 1//
def hanoi(n, start, mid, to):
hanoi(n - 1, start, mid, to)
[start, to]
hanoi(n - 1, mid, to, start)
hanoi(3, 1, 3, 2)
//๊ณผ์ 2//
def hanoi(n, start, to, mid, answer):
if n == 1:
return answer.append([start, to])
hanoi(n - 1, start, mid, to, answer)
answer.append([start, to])
hanoi(n - 1, mid, to, start, answer)
//์ต์ข
์ ๋ต//
def hanoi(n, start, to, mid, answer):
if n == 1:
return answer.append([start, to])
hanoi(n - 1, start, mid, to, answer)
answer.append([start, to])
hanoi(n - 1, mid, to, start, answer)
def solution(n):
answer = []
hanoi(n, 1, 3, 2, answer)
return answer