알고리즘/재귀

[프로그래머스] 하노이의 탑 (재귀) - Java

2023. 4. 19. 10:20
목차
  1. 문제 상황
  2. 문제 설명
  3. 제한사항
  4. 입출력 예
  5. 입출력 예 설명
  6. 문제 풀이

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

문제 상황

문제 설명

하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.

  1. 한 번에 하나의 원판만 옮길 수 있습니다.
  2. 큰 원판이 작은 원판 위에 있어서는 안됩니다.

하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.

1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.

제한사항

  • n은 15이하의 자연수 입니다.

입출력 예

n result
2 [ [1,2], [1,3], [2,3] ]

입출력 예 설명

입출력 예 #1다음과 같이 옮길 수 있습니다.

 

 

문제 풀이

class Solution {
    static int count = 0;
    static int[][] answer;
    public int[][] solution(int n) {
        answer = new int[(int)(Math.pow(2,n)-1)][2];
        
        Hanoi(n, 1, 2, 3);
        
        return answer;
    }

    public static void Hanoi(int n, int start, int mid, int end) {
        if (n == 1) {
            answer[count][0] = start;
            answer[count][1] = end;
            count++;
            return;
        }

        Hanoi(n - 1, start, end, mid);
        answer[count][0] = start;
        answer[count][1] = end;
        count++;
        Hanoi(n - 1, mid, start, end);
    }
}

 

저작자표시 (새창열림)

'알고리즘 > 재귀' 카테고리의 다른 글

[백준] 11729 하노이 탑의 이동순서 (재귀) - Java  (0) 2023.03.30
  1. 문제 상황
  2. 문제 설명
  3. 제한사항
  4. 입출력 예
  5. 입출력 예 설명
  6. 문제 풀이
'알고리즘/재귀' 카테고리의 다른 글
  • [백준] 11729 하노이 탑의 이동순서 (재귀) - Java
jny0
jny0
성장일기
jny0
J N Y 0
jny0
  • 분류 전체보기 (192)
    • 트러블슈팅 (6)
    • Java (22)
    • HTML, CSS , JavaScript (7)
    • MySQL, DBMS (9)
    • GIT (6)
    • 객체지향의 사실과 오해 (3)
    • 자바 ORM 표준 JPA 프로그래밍 (13)
    • 알고리즘 (114)
      • 자료구조 (59)
      • 수학 (11)
      • 정렬 (2)
      • 그리디 (3)
      • DP (4)
      • 그래프 (3)
      • 탐색 (9)
      • 재귀 (2)
      • 문자열 (9)
      • 기타 (12)
    • CS (10)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 글쓰기
  • 관리

공지사항

인기 글

태그

  • Java
  • BFS
  • DP
  • git
  • 알고리즘
  • method
  • 프로그래머스
  • 그리디
  • db
  • 스택
  • MySQL
  • 누적합
  • 투포인터
  • 구현
  • 자료구조
  • codeup
  • JPA
  • JS
  • 영상후기
  • 백준

최근 댓글

최근 글

hELLO · Designed By 정상우.
jny0
[프로그래머스] 하노이의 탑 (재귀) - Java
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.