11729 : 하노이 탑 이동순서

11729 : 하노이 탑 이동순서#

supposed to be surdarla logo

Surdarla

Dec 01 Fri 09:38, 2023

1 min read

  • https://d2gd6pc034wcta.cloudfront.net/tier/10.svg 골드 5

시간제한

메모리제한

정답비율

1초

256MB

50.536%

문제#

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

한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

hanoi fig

Fig. 15 그림은 원판이 5개인 경우의 예시이다.#

input#

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

output#

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

think#

하노이 탑은 기본적으로 백트레킹 문제이다. 여기서 이동 순서에 대해서 출력을 해야한다. 그런데 이동횟수가 최소가 되어야한다는 조건이 달려있다.

python#

import sys, os

problem_num = "11729"

path = os.getcwd() + f"\\txt\\{problem_num}" + ".txt"
sys.stdin = open(path, "r")
input = sys.stdin.readline

n = int(input())

result = []


def move(start, to):
    return [start, to]


def hanoi(n, start, to, via):
    if n == 1:
        result.append(move(start, to))
    else:
        hanoi(n - 1, start, via, to)
        result.append(move(start, to))
        hanoi(n - 1, via, to, start)
    return result

answer = hanoi(n, 1, 3, 2)
print(len(answer))
for i in answer:
    print(*i)

7
1 3
1 2
3 2
1 3
2 1
2 3
1 3

javascript#

Listing 11 nodejs code#
 1const problem_num = "11729";
 2const path = `${__dirname}\\txt\\${problem_num}.txt`;
 3// const path = "/dev/stdin";
 4
 5const input = require("fs").readFileSync(path, 'utf8').toString().trim().split('\n');
 6let currentLine = 0;
 7
 8function readLine() {
 9    return input[currentLine++].split(' ').map(Number);
10}
11
12const n = parseInt(readLine()[0]);
13let moves = [];
14
15function hanoi(n, start, to, via) {
16    if (n == 1) {
17        moves.push(`${start} ${to}`);
18    } else {
19        hanoi(n - 1, start, via, to);
20        moves.push(`${start} ${to}`);
21        hanoi(n - 1, via, to, start)
22    }
23    return moves
24}
25
26let answer = hanoi(n, 1, 3, 2);
27console.log(moves.length);
28console.log(moves.join('\n'));

  • 숫자 하나만을 받으므로 [0] 인덱스 접근

  • 짜피 print해야함으로 `, $ 를 이용해서 변수 받아서 string해주기

java#

Listing 12 java block#
 1import java.io.*;
 2import java.util.*;
 3
 4public class Main {
 5    public static void main(String[] args) throws IOException {
 6        String problemNumber = "11729";
 7        String path = System.getProperty("user.dir") + "\\scripts\\algorithm\\problem\\txt\\" + problemNumber + ".txt";
 8        BufferedReader br = new BufferedReader(new FileReader(path));
 9        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
10        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
11        // StringTokenizer st = new StringTokenizer(br.readLine());
12
13        int n = Integer.parseInt(br.readLine());
14        br.close();
15        StringBuilder sb = new StringBuilder();
16        int moveCount = hanoi(n, 1, 2, 3, sb);
17
18        bw.write(moveCount + "\n");
19        bw.write(sb.toString());
20        bw.flush();
21        bw.close();
22    }
23
24    public static int hanoi(int n, int start, int via, int to, StringBuilder sb) {
25        if (n == 1) {
26            sb.append(start).append(" ").append(to).append("\n");
27            return 1;
28        } else {
29            int count1 = hanoi(n - 1, start, to, via, sb);
30            sb.append(start).append(" ").append(to).append("\n");
31            int count2 = hanoi(n - 1, via, start, to, sb);
32            return count1 + count2 + 1;
33        }
34    }
35}

  • 맨처음엔 그냥 하니깐 시간초과가 나옴

  • System.out을 사용하면 엄청 느려서 모아놨다가 한번에 출력하는 StringBuilder에 가져다 붙여놨다가 한번에 출력하는 방식으로 해야함.

  • 굳이 이렇게까지 불편하게 해야하나 싶음. python은 신이다.

  • 하지만 메모리면에서는 java가 48412kb로 javascript(153640kb), python(123336kb)인 것에 비해서 굉장히 큰 이점이 존재하는 것은 맞는 것으로 보인다.

  • string에는 append, list에는 add… 정말루다가 너무 헤깔린다.

Contents