๐ŸŒ[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ํ•˜๋…ธ์ด์˜ ํƒ‘

Chobbyยท2022๋…„ 6์›” 10์ผ
1

Programmers

๋ชฉ๋ก ๋ณด๊ธฐ
33/344

ํ•ด๋‹น ๊ฒŒ์‹œ๋ฌผ์€ johnyejin๋‹˜์˜ [JavaScript] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค ํ•˜๋…ธ์ด์˜ ํƒ‘ LEVEL3 ๊ฒŒ์‹œ๋ฌผ์„ ๋ณด๊ณ  ์ฐธ๊ณ ํ•˜์—ฌ ์ œ์ž‘๋˜์—ˆ์Œ์„ ๋ฏธ๋ฆฌ ๋ฐํž™๋‹ˆ๋‹ค.

๐Ÿš—๋ฌธ์ œ ์„ค๋ช…

ํ•˜๋…ธ์ด ํƒ‘(Tower of Hanoi)์€ ํผ์ฆ์˜ ์ผ์ข…์ž…๋‹ˆ๋‹ค. ์„ธ ๊ฐœ์˜ ๊ธฐ๋‘ฅ๊ณผ ์ด ๊ธฐ๋™์— ๊ฝ‚์„ ์ˆ˜ ์žˆ๋Š” ํฌ๊ธฐ๊ฐ€ ๋‹ค์–‘ํ•œ ์›ํŒ๋“ค์ด ์žˆ๊ณ , ํผ์ฆ์„ ์‹œ์ž‘ํ•˜๊ธฐ ์ „์—๋Š” ํ•œ ๊ธฐ๋‘ฅ์— ์›ํŒ๋“ค์ด ์ž‘์€ ๊ฒƒ์ด ์œ„์— ์žˆ๋„๋ก ์ˆœ์„œ๋Œ€๋กœ ์Œ“์—ฌ ์žˆ์Šต๋‹ˆ๋‹ค. ๊ฒŒ์ž„์˜ ๋ชฉ์ ์€ ๋‹ค์Œ ๋‘ ๊ฐ€์ง€ ์กฐ๊ฑด์„ ๋งŒ์กฑ์‹œํ‚ค๋ฉด์„œ, ํ•œ ๊ธฐ๋‘ฅ์— ๊ฝ‚ํžŒ ์›ํŒ๋“ค์„ ๊ทธ ์ˆœ์„œ ๊ทธ๋Œ€๋กœ ๋‹ค๋ฅธ ๊ธฐ๋‘ฅ์œผ๋กœ ์˜ฎ๊ฒจ์„œ ๋‹ค์‹œ ์Œ“๋Š” ๊ฒƒ์ž…๋‹ˆ๋‹ค.

  1. ํ•œ ๋ฒˆ์— ํ•˜๋‚˜์˜ ์›ํŒ๋งŒ ์˜ฎ๊ธธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
  2. ํฐ ์›ํŒ์ด ์ž‘์€ ์›ํŒ ์œ„์— ์žˆ์–ด์„œ๋Š” ์•ˆ๋ฉ๋‹ˆ๋‹ค.

ํ•˜๋…ธ์ด ํƒ‘์˜ ์„ธ ๊ฐœ์˜ ๊ธฐ๋‘ฅ์„ ์™ผ์ชฝ ๋ถ€ํ„ฐ 1๋ฒˆ, 2๋ฒˆ, 3๋ฒˆ์ด๋ผ๊ณ  ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. 1๋ฒˆ์—๋Š” n๊ฐœ์˜ ์›ํŒ์ด ์žˆ๊ณ  ์ด n๊ฐœ์˜ ์›ํŒ์„ 3๋ฒˆ ์›ํŒ์œผ๋กœ ์ตœ์†Œ ํšŸ์ˆ˜๋กœ ์˜ฎ๊ธฐ๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

1๋ฒˆ ๊ธฐ๋‘ฅ์— ์žˆ๋Š” ์›ํŒ์˜ ๊ฐœ์ˆ˜ n์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, n๊ฐœ์˜ ์›ํŒ์„ 3๋ฒˆ ์›ํŒ์œผ๋กœ ์ตœ์†Œ๋กœ ์˜ฎ๊ธฐ๋Š” ๋ฐฉ๋ฒ•์„ returnํ•˜๋Š” solution๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.

๐Ÿš“์ œํ•œ ์‚ฌํ•ญ

  • n์€ 15์ดํ•˜์˜ ์ž์—ฐ์ˆ˜ ์ž…๋‹ˆ๋‹ค.

๐Ÿš•์ž…์ถœ๋ ฅ ์˜ˆ

nresult
2[ [1,2], [1,3], [2,3] ]

์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…
์ž…์ถœ๋ ฅ ์˜ˆ #1
๋‹ค์Œ๊ณผ ๊ฐ™์ด ์˜ฎ๊ธธ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.



๐Ÿ›บ๋‚˜์˜ ํ’€์ด

function solution(n) {
    const answer = []
    function hanoi(depth, from, to, mid) {
      	// ํ•˜๋‚˜์˜ ์›ํŒ๋งŒ ์žˆ๋Š” ๊ฒฝ์šฐ ์‹œ์ž‘์ง€์ , ๋„์ฐฉ์ง€์  ์œผ๋กœ ๋ฐฐ์—ด์— ๊ฐ’์„ ๋„ฃ๊ณ  ์ข…๋ฃŒ
        if(depth === 1) answer.push([from,to])
        else {
          	// ๋‹ค์Œ ์›ํŒ์€ ์‹œ์ž‘์ง€์  ์—์„œ ์ค‘๊ฐ„ ์ง€์ ์œผ๋กœ
            hanoi(depth-1, from, mid, to)
          	// ์ด๋™ ๊ฒฝ๋กœ ํ‘œ์‹œ
            answer.push([from, to])
          	// ์ค‘๊ฐ„ ์ง€์ ์—์„œ ๋„์ฐฉ ์ง€์ ์œผ๋กœ
            hanoi(depth-1, mid, to, from)
        }
    }
    hanoi(n, 1, 3, 2)
    return answer
}

ํ•˜๋…ธ์ด ๊ณต์‹์„ ๋ณด๋ฉด์„œ ๋Š๋‚€์ ์€ ๋”ฑํžˆ ์ดํ•ดํ•˜๊ฑฐ๋‚˜ ํ•  ํ•„์š” ์—†์ด ์งง์€ ๊ตฌ๋ฌธ์„ ์™ธ์šฐ๋Š”๊ฒŒ ๋” ํŽธํ•  ๊ฑฐ ๊ฐ™๋‹ค๊ณ  ๋Š๊ผˆ์Œ..

๋ณธ์ธ ํ’€์ด ๋‹น์‹œ์— 3LV ์ด์˜€๋˜ ๋ฌธ์ œ๋Š” ํ’€์ด ์™„๋ฃŒ ์‹œ์  ๊ธฐ์ค€ 2LV ๊นŒ์ง€ ๋–จ์–ด์กŒ์Šต๋‹ˆ๋‹ค..

๊ทธ๋Ÿผ ๋ฟ…-

profile
๋‚ด ์ง€์‹์„ ๊ณต์œ ํ•  ์ˆ˜ ์žˆ๋Š” ๋Œ€๋‹ดํ•จ

0๊ฐœ์˜ ๋Œ“๊ธ€