[알고리즘] 백준 - 하노이 탑 이동 순서

백준 - 하노이 탑 이동 순서

내 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class baekjoon_11729 {

    static List<List<Integer>> list = new ArrayList<>();
    static int callCount = 0;
    static List pathList = new ArrayList();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        List stack0 = new ArrayList();
        List stack1 = new ArrayList();
        List stack2 = new ArrayList();
        for (int i = N; i > 0; i--) {
            stack0.add(i);
        }
        list.add(stack0);
        list.add(stack1);
        list.add(stack2);

        solve(0, 1, 2, N);
        System.out.println(callCount);
        for (Object path : pathList) {
            bw.write(String.join(" ", (List) path)+"\n");
        }
        bw.flush();
        bw.close();
    }

    private static void solve(int start, int stopover, int destination, int count) {
        if (count == 1) {
            move(start, destination);
            return;
        }

        solve(start, destination, stopover, count-1); // 제일 밑의 원판을 목표지점으로 옮기기 위해 위에 것들을 stopover에 잠시 놔둔다.
        move(start, destination);
        solve(stopover, start, destination, count - 1);
    }

    private static void move(int start, int destination) {
        callCount += 1;
        List startDest = new ArrayList();
        startDest.add(Integer.toString(start + 1));
        startDest.add(Integer.toString(destination + 1));
        pathList.add(startDest);

        list.get(destination).add(list.get(start).remove(list.get(start).size()-1));
    }
}

로직은 비교적 간단하다. n개의 원판이 있을 때 우선 n-1개의 원판을 2번으로 옮긴뒤 맨밑 원판을 3번으로 옮기고, n-1개의 원판을 3번으로 옮기는 것이다.

처음에는 Stack을 List로 저장해서 쓰려고 했으나 저장은 되는데, List에서 get을 이용해서 꺼내서 add를 쓰려고 하니 되지 않았다. 이 이유에 대해 알아보자.

이중리스트를 사용해보았다. 확실히 파이썬의 리스트보다 불편하지만 익숙해지도록 하자.

속도 초과가 나서 BufferedWriter를 사용하였다. write후 flush, close까지 해주자.

for each에서 item은 object만 되었다. 따라서 이중리스트 같은 경우 Object로 캐스팅을 해줬어야 했다.

String.join() 함수를 이용해 List의 요소들을 join해서 출력할 수 있었다.