[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.3 -ํ•˜๋…ธ์ด์˜ ํƒ‘(C++)

2023. 7. 22. 16:44ยท๐Ÿ–ฅ๏ธ Study Note/Coding Test

https://school.programmers.co.kr/learn/courses/30/lessons/12946

๋ฌธ์ œ ์„ค๋ช…

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

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

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

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

๋‚ด ํ’€์ด

์žฌ๊ท€์˜ ๊ฝƒ ํ•˜๋…ธ์ด์˜ ํƒ‘ ๋ฌธ์ œ! ์˜ˆ์ „์—๋Š” ์ •๋ง ์–ด๋ ต๊ฒŒ ๋А๊ปด์กŒ๋Š”๋ฐ ๋‹ค์‹œ ํ’€์–ด๋ณด๋‹ˆ ์ดํ•ด๊ฐ€ ์–ด๋ ต์ง€ ์•Š์•˜๋‹ค.

#include <string>
#include <vector>

using namespace std;

void MoveDisk(vector<vector<int>>& answer, int n, int start, int dest)
{
    // ์˜ฎ๊ธฐ๋ ค๋Š” ์›ํŒ์ด 1๊ฐœ์ธ ๊ฒฝ์šฐ ์˜ฎ๊ธฐ๊ณ  ๋ฐ˜ํ™˜ํ•ด์ค€๋‹ค
    if(n == 1)
    {
        answer.push_back({start, dest});
        return;
    }
    
    // n-1 ๊ฐœ์˜ ์›ํŒ์„ ์‹œ์ž‘์  ํ˜น์€ ๋ชฉํ‘œ์ง€์ ์ด ์•„๋‹Œ ๋‚˜๋จธ์ง€ ๊ธฐ๋‘ฅ์œผ๋กœ ์˜ฎ๊ธด๋‹ค.
    MoveDisk(answer, n-1, start, 6-start-dest);
    
    // n๋ฒˆ์งธ ์›ํŒ์„ ๋ชฉํ‘œ์‹œ์ ์œผ๋กœ ์˜ฎ๊ธด๋‹ค.
    answer.push_back({start, dest});
    
    // ๋‚˜๋จธ์ง€ ๊ธฐ๋‘ฅ์œผ๋กœ ์˜ฎ๊ฒจ์ง„ n-1๊ฐœ์˜ ์›ํŒ์„ ๋ชฉํ‘œ ์ง€์ ์œผ๋กœ ์˜ฎ๊ธด๋‹ค.
    MoveDisk(answer, n-1,  6-start-dest, dest);
    
    
}

vector<vector<int>> solution(int n) {
    vector<vector<int>> answer;

    MoveDisk(answer, n, 1, 3);
    
    return answer;
}
์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'๐Ÿ–ฅ๏ธ Study Note > Coding Test' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - [์นด์นด์˜ค ์ธํ„ด] ์ˆ˜์‹ ์ตœ๋Œ€ํ™”(C++)  (0) 2023.07.24
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ์—ฐ์† ๋ถ€๋ถ„ ์ˆ˜์—ด ํ•ฉ์˜ ๊ฐœ์ˆ˜(C++)  (0) 2023.07.23
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ์บ์‹œ(C++)  (0) 2023.07.20
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ํŠœํ”Œ(C++)  (0) 2023.07.18
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ์  ์ฐ๊ธฐ(C++)  (0) 2023.07.17
'๐Ÿ–ฅ๏ธ Study Note/Coding Test' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - [์นด์นด์˜ค ์ธํ„ด] ์ˆ˜์‹ ์ตœ๋Œ€ํ™”(C++)
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ์—ฐ์† ๋ถ€๋ถ„ ์ˆ˜์—ด ํ•ฉ์˜ ๊ฐœ์ˆ˜(C++)
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ์บ์‹œ(C++)
  • [ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.2 - ํŠœํ”Œ(C++)
Beankong_
Beankong_
์ฃผ๋‹ˆ์–ด ํด๋ผ์ด์–ธํŠธ ํ”„๋กœ๊ทธ๋ž˜๋จธ ๊ณต๋ถ€ ๊ธฐ๋ก
  • Beankong_
    Beankong's Devlog
    Beankong_
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
    • ์ „์ฒด ๊ธ€ (146)
      • โ›… Daily (0)
      • ๐Ÿ–ฅ๏ธ Study Note (2)
        • C++ (1)
        • Unreal Engine (5)
        • Coding Test (123)
        • Design Patteren (5)
        • VCS (Git..) (1)
        • Server (1)
      • ๐Ÿงญ Devlog (8)
        • ์˜ค๋‹ต๋…ธํŠธ (4)
        • UE5 GameLift Server Test Project (1)
        • TIL (3)
  • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.3
Beankong_
[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค]level.3 -ํ•˜๋…ธ์ด์˜ ํƒ‘(C++)
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”