dev_beomgeun
꾸준하게 차근차근
dev_beomgeun
전체 방문자
오늘
어제
  • 분류 전체보기 (170)
    • 전공 (0)
      • 운영체제 (0)
      • 알고리즘 (0)
      • 자료구조 (0)
      • 데이터베이스 (0)
      • 네트워크 (0)
    • 개발 공부 (32)
      • 웹 (6)
      • 리눅스 (4)
      • 머신러닝 (1)
      • 스프링 (17)
      • Git (2)
      • AWS (2)
    • 개발 도서, 강의 (3)
      • 스프링 입문을 위한 자바 객체지향의 원리와 이해 (0)
      • 모든 개발자를 위한 HTTP 웹 기본 지식(김영한.. (2)
      • 스프링 부트와 AWS로 혼자 구현하는 웹서비스 (1)
    • 문제 풀이 (118)
      • 백준 알고리즘 (72)
      • 프로그래머스 알고리즘, SQL (38)
      • Hackerrank SQL (8)
    • 프로젝트 기록 (4)
      • 캡스톤 종합설계 (4)
      • 반려하루 프로젝트 (0)
    • 활동 기록 (12)
      • 네이버 부스트캠프 (7)
      • 취준 & 코테 (4)
      • 소프트웨어 마에스트로 13기 (1)
    • 이것저것 (1)

블로그 메뉴

  • 홈
  • 깃허브
  • 링크드인
  • 방명록

공지사항

인기 글

태그

  • 스프링
  • 일기
  • HackerRank mysql
  • 네이버 부스트캠프
  • 프로그래머스
  • 프로그래머스 SQL
  • dp
  • 백준
  • AI Tech
  • 그래프탐색
  • 부스트캠프
  • Baekjoon
  • 반성
  • 서블릿
  • Hackerrank
  • c++
  • 기록
  • 백준 DP
  • BFS
  • 회고

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
dev_beomgeun

꾸준하게 차근차근

문제 풀이/백준 알고리즘

[baekjoon 11729] 하노이의 탑 이동 순서 (재귀 호출) (C++)

2021. 2. 9. 17:37
728x90

www.acmicpc.net/problem/11729

 

11729번: 하노이 탑 이동 순서

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로

www.acmicpc.net

유명한 하노이의 탑 문제이다.

 

재귀를 하나하나 따라가며 이해해보려고 했는데 쉽지가 않았다.

 

재귀를 이용한 문제는 재귀의 모든 흐름을 파악하기보다는, 호출의 의미와 재귀 함수와 호출의 관계를 생각해야겠다.

 

하노이의 탑의 공식은

1. N-1개의 원판을 첫 번째 기둥에서 두 번째 기둥으로 옮기고

2. 마지막 하나 남은 원판을 첫 번째 기둥에서 세 번째 기둥으로 옮기고(출력)

- 하나의 원판을 옮기는 경우가 실질적인 하노이의 탑 이동 순서이기 때문이다.

3. 그리고 옮겨놨던 N-1개의 원판을 두 번째 기둥에서 세 번째 기둥으로 옮긴다.

 

이 공식을 함수 호출로 옮겨보면

void hanoi(int N, int from, int by, int to)가 기본 틀이다. ( 개수, 첫 번째, 두 번째, 세 번째)

1. hanoi(N-1, from, to, by)

-> 기본 틀이 두 번째와 네 번째 인자가 from에서 to이다.

우리는 지금 첫 번째에서 두 번째로 옮기는 것이기에 to자리에 두 번째를 뜻하는 by인자가 들어간다.

2. v.push_back(make_pair(from, to))

-> 하나의 원판을 첫 번째에서 세 번째로 옮기기에 그대로 첫 번째 인자와 세 번째 인자를 출력해준다.

3. hanoi(N-1, by, from, to)

-> 두 번째에서 세 번째로 옮기는 것이기에 by와 to가 각각 첫 번째 인자와 세 번째 인자로 들어간다.

 

이렇게 재귀를 진행해주면 된다.

하나하나 재귀를 따라가기엔 힘들다.

 

#include <iostream>
#include <vector>
using namespace std;
vector<pair<int, int>> v;

void hanoi(int n, int from, int by, int to) {
	if (n == 1)
		v.push_back(make_pair(from, to));
	else {
		hanoi(n - 1,from, to, by);
		v.push_back(make_pair(from, to));
		hanoi(n - 1, by, from, to);
	}
}
int n;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	hanoi(n, 1, 2, 3);
	cout << v.size()<<"\n";
	for (int i = 0; i < v.size(); i++) {
		cout << v[i].first << " " << v[i].second << "\n";
	}
}

 

 

728x90
저작자표시 비영리 변경금지 (새창열림)

'문제 풀이 > 백준 알고리즘' 카테고리의 다른 글

[baekjoon 1326] 폴짝폴짝 (BFS) (C++)  (0) 2021.02.13
[baekjoon 2447] 별 찍기 - 10 (재귀 호출) (C++)  (0) 2021.02.09
[baekjoon 2146] 다리 만들기 (그래프, BFS) (C++)  (0) 2021.02.08
[baekjoon 2110] 공유기 설치 (이진탐색) (C++)  (0) 2021.02.07
[baekjoon 11725] 트리의 부모 찾기- 트리, 그래프, BFS, DFS (C++)  (0) 2021.02.05
    '문제 풀이/백준 알고리즘' 카테고리의 다른 글
    • [baekjoon 1326] 폴짝폴짝 (BFS) (C++)
    • [baekjoon 2447] 별 찍기 - 10 (재귀 호출) (C++)
    • [baekjoon 2146] 다리 만들기 (그래프, BFS) (C++)
    • [baekjoon 2110] 공유기 설치 (이진탐색) (C++)
    dev_beomgeun
    dev_beomgeun
    백엔드 개발을 하며 얻은 지식과 경험을 공유합니다. 현재 카카오페이에서 백엔드 엔지니어로 일하고 있습니다.

    티스토리툴바