[프로그래머스] 하노이의 탑

gcoco·2023년 5월 16일

안녕하세요! 일찍 일어난 GCOCO입니다!

어제는 스승의 날이었지요?
다들 스승님을 찾아뵙고 좋은 시간을 보내셨는지 모르겠습니다.
부디 좋은 하루를 보내셨으면 하는 바람이군요!
아무쪼록, 어제는 제 수업의 교수님께서도 제자분들이 찾아왔습니다. 한 마디로 제 선배님들이죠.
선배님들은 개발자로 일을 하고 계신데 상당히 강조해 주셨던 부분이 바로 CS전공 지식이었습니다!

강조해 주신 부분은 다음과 같습니다.

네트워크
자료구조와 알고리즘
DATABASE
시스템 프로그래밍
OS(Operating System)

이러한 전공지식들은 정말 평생 사용하기에 기초가 탄탄히 닦여 있어야 한다고 하셨습니다.
그렇기에! 부족한 부분들을 하나씩 채워가려고 합니다.
두루뭉실하게 '뭘 해야겠다~' 라고 생각했을땐 여유롭다고 생각했지만 막상 구체적인 목표가 생기니 굉장히 할 일이 많음이 느껴집니다.
하지만 '천 리 길도 한 걸음부터'라는 속담이 있듯이, 나아가는 것이 중요한 법!

차근차근 나아가도록 하겠습니다!

하노이 탑 문제

하노이 탑 문제는 다음과 같습니다.

문제 : 막대 A,B,C가 존재하고 막대 A에 쌓여있는 원판 n개를 막대 C로 옮기는 것이다.

다음과 같은 규칙이 있다.

한 번에 하나의 원판만 이동 가능하다
맨 위 원판만 이동 가능하다.
크기가 작은 원판 위에 큰 원판이 쌓일 수 없다.
중간 막대를 임시적 이용 가능하나 1,2,3의 조건을 지켜야 한다.

해결

하노이 탑 문제는 대표적인 순환(recursion) 문제입니다. 핵심 아이디어는 다음과 같습니다.

C를 임시 버퍼로 사용하여 A에 쌓여있는 n-1개의 원판을 B로 옮긴다.
A의 가장 큰 원판을 C로 옮긴다.
A를 임시버퍼로 사용하여 B에 쌓여있는 n-1개의 원판을 C로 옮긴다.

이를 pseudocode로 작성해보면 다음과 같습니다.

//from에 쌓여있는 n개의 원판을 tmp를 이용하여 to로 옮긴다.
void hanoi_tower(int n,char from,char tmp, char to){
	if(n==1)
    	from에서 to로 원판을 옮긴다.
    else{
    	from에 쌓여있는 n-1개의 원판을 to를 이용하여 tmp로 옮긴다.
    	hanoi_tower(n-1,from,to,tmp)
    	tmp에 쌓여있는 n-1개의 원판을 from를 이용하여 to로 옮긴다.
    }
}

코드로 구현하면 다음과 같습니다.

#include <iostream>

using namespace std;
void hanoi_tower(int n, char from, char tmp, char to) {
	if(n==1)
		cout << "원판 1을 " << from << "에서 " << to << "으로 옮긴다." << endl;
	else {
		//n-1개의 원판을 to를 이용하여 tmp로 옮긴다.
		hanoi_tower(n - 1, from, to, tmp);
		cout << "원판 "<<n<<"을 " << from << "에서 " << to << "으로 옮긴다." << endl;


		//from이 비었으므로, tmp에 있는 n-1개의 원판을 to로 옮긴다.
		hanoi_tower(n - 1, tmp, from, to);
	}
}


int main() {
	hanoi_tower(3, 'A', 'B', 'C');
	return 0;
}

n=3일때의 출력은 아래와 같습니다.

n=4일때의 출력은 아래와 같습니다.

이를 응용하여 문제를 풀어 봅시다!
문제링크:

풀이

#include <string>
#include <vector>

using namespace std;
void hanoi(vector<vector<int>>& answer,int n,int from, int tmp, int to){
    if(n==1){
        vector<int> t(2,0);
        t[0]=from;
        t[1]=to;
        answer.emplace_back(t);
    }
    else{
        hanoi(answer,n-1,from,to,tmp);
        vector<int> t(2,0);
        t[0]=from;
        t[1]=to;
        answer.emplace_back(t);
        hanoi(answer,n-1,tmp,from,to);
    }
    
}

vector<vector<int>> solution(int n) {
    vector<vector<int>> answer;
    hanoi(answer,n,1,2,3);
    return answer;
}