๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์ฝ”๋”ฉํ…Œ์ŠคํŠธ/ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

[Javascript] ํ•˜๋…ธ์ด์˜ ํƒ‘ (12946) - fail

๋ฌธ์ œ๋งํฌ

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ํ•˜๋…ธ์ด์˜ ํƒ‘

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

programmers.co.kr

 

์ ‘๊ทผ ๋ฐฉ๋ฒ•

์ฒ˜์Œ์— ์ถœ๋ ฅ๊ฐ’์„ ์ œ๋Œ€๋กœ ์•ˆ๋ณด๊ณ  ํ•˜๋…ธ์ด์˜ ํƒ‘์˜ ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ๋กœ ์ฐฉ๊ฐํ•˜์—ฌ
๋„ˆ๋ฌด ์‰ฝ๋‹ค๊ณ  ์ƒ๊ฐํ•˜๋ฉฐ ๊ทœ์น™์„ ์ฐพ์•˜๋‹ค.

๊ทธ๋Ÿฌ๋‚˜ ๋‹ค์‹œ ์ž์„ธํžˆ ๋ณด๋‹ˆ ๋‹จ์ˆœํžˆ ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ฐพ๋Š” ๊ฒƒ์ด ์•„๋‹Œ ์ด๋™ ์ขŒํ‘œ๋ฅผ ์ฐพ๋Š” ๋ฌธ์ œ์˜€๊ณ 

์ž‘์€ ์ˆ˜์—์„œ ํŒจํ„ด์„ ์ฐพ์•„๋ณด๋ ค ํ–ˆ๋Š”๋ฐ.. ์žฌ๊ท€ ๊ฐ™๊ธฐ๋„ ํ•˜๊ณ , dp ๊ฐ™๊ธฐ๋„ ํ•œ ๊ฒƒ์ด ๋ฐฉํ–ฅ์„ ์ฐพ์ง€ ๋ชปํ–ˆ๋‹ค.
(๊ทธ๋‚˜๋งˆ n์ด ์ง์ˆ˜์ผ๋•Œ, ํ™€์ˆ˜์ผ๋•Œ ์ดˆ๋ฐ˜ ์ด๋™์€ ๊ฐ™๋‹ค๋Š” ๊ฒƒ์€ ์•Œ ์ˆ˜ ์žˆ์—ˆ๋‹ค.)

๊ณ„์† ๊ณ ๋ฏผํ•ด๋„ ๋ฐฉ๋ฒ•์ด ๋– ์˜ค๋ฅด์ง€ ์•Š์•„ ๊ตฌ๊ธ€์˜ ํž˜์„ ๋นŒ๋ ธ๋Š”๋ฐ
์•„์ง๋„ ์žฌ๊ท€์ ์ธ ๋ฐฉ์‹์—๋Š” ๋จธ๋ฆฌ๊ฐ€ ๋”ฐ๋ผ๊ฐ€์ง€ ๋ชปํ•˜๋Š” ๊ฒƒ ๊ฐ™๋‹ค..

์Šค๋‹ˆํŽซ์„ ์ด์šฉํ•ด ์ดํ•ด์— ๋„์›€์„ ๋ฐ›์„ ์ˆ˜ ์žˆ์—ˆ๋‹ค.

์ฐธ๊ณ  ๋ธ”๋กœ๊ทธ

function solution(n) {
    var answer = [];
    
    const hanoi = (n, src, dst, mid) => {
    
        if (n === 1) answer.push([src, dst]);
        else {
            hanoi(n - 1, src, mid, dst);
            answer.push([src, dst]);
            hanoi(n - 1, mid, dst, src);
        }
    }
    
    hanoi(n, 1, 3, 2);

    return answer;
}