문제 간단 해석
원판을 규칙에 맞게 옮기는 문제. 기준 위의 원판들을 치우고, 기준 원판을 옮기고, 나머지 원판을 기준 원판 위에 올리는 방향으로 생각하면 쉬울 수 있다.
Java
간단한 재귀함수를 통해 구현.
풀이 코드
import java.util.List;
import java.util.ArrayList;
class Solution {
private List<int[]> list = new ArrayList<>();
public void move(int target, int now, int to, int another) {
if (target == 0) {
return;
}
move(target - 1, now, another, to);
list.add(new int[] {now, to});
move(target - 1, another, to, now);
}
public int[][] solution(int n) {
move(n, 1, 3, 2);
return list.toArray(new int[list.size()][]);
}
}해석
private List<int[]> list = new ArrayList<>();
...
public int[][] solution(int n) {
move(n, 1, 3, 2);
return list.toArray(new int[list.size()][]);
}값들을 담을 list 준비. 미리 공간을 계산해서 처음부터 2차원 배열로 만들었다면 더 좋을 것 같다.
n번째 원판을 1에서 3으로 옮기게끔 한다. 재귀를 통해 원반을 최종적으로 완성하게 되면, list를 2차원 int 배열로 만들어 반환한다.
public void move(int target, int now, int to, int another) {
if (target == 0) {
return;
}
move(target - 1, now, another, to);
list.add(new int[] {now, to});
move(target - 1, another, to, now);
}target 위의 원판들을 다른 공간으로 옮기고, target 원판을 현재 위치에서 목표 위치로 옮긴다. 그 후 target 위의 원판들을 target 원판 위로 올리게끔 한다.
4개짜리 원판으로 예시를 들어보도록 하겠다.
좌측 글씨 한줄이 각각의 재귀 스택을 나타낸다.
검은 글씨는 첫 생성된 이동 명령이며, 붉은 글씨는 명령이 수행된 이후이다.
우리가 원하는 건, 4번째 원판부터 1번째 원판까지 모두 3번 기둥으로 옮기는 것이다.
4번째 원판을 3번 기둥으로 옮기게끔 명령하면, 재귀가 수행되며 위의 원판들을 빈 기둥인 2번과 목표인 3번으로 번갈아 옮기라는 명령을 전달한다.
1번째 원판이 2번 원판으로 전달된다. 1번째 원판이 본인보다 작은 원판을 불러들이는 명령을 내리나, 1번째 원판보다 작은 원판은 존재하지 않으므로 무효된다.
2번째 원판이 3번 원판으로 전달된다.
이 때, 2번째 원판은 1번째 원판을 현재 위치로 불러들이는 명령을 생성한다.
1번째 원판이 3번 기둥으로 이동한다.
1번째 원판은 더 불러들일 것이 없으니 끝.
3번째 원판은 2번 기둥으로 옮겨지고, 마찬가지로 2번째 원판을 불러들인다.
2번째 원판은 위의 1번째 원판을 옮겨야 하기에, 1번째 원판에게 이동 명령을 내린다.
2번째 원판은 2번 기둥으로 옮겨지고, 다시 1번 원판을 불러들인다.
그 후 4번째 원판이 3번 기둥으로 옮겨진다.
4번째 원판은 3번째 원판을 호출, 3번째 원판부터 1번째까지 이동명령을 생성한다.
1번째 원판이 3번 기둥으로 이동.
그 후 2번째 원판이 1번 기둥으로 이동, 1번째 원판을 불러들인다.
1번째 원판은 1번 기둥으로 이동.
3번째 원판이 3번 기둥으로 이동되며, 2번째 원판과 1번째 원판의 이동명령을 생성한다.
1번째 원판이 2번 기둥으로 이동.
2번째 원판이 3번 기둥으로 옮겨지며 1번째 원판의 이동명령을 생성한다.
1번째 원판이 3번 기둥으로 이동.
모든 원판이 이동되고, 재귀 스택이 사라지며 수행이 끝나게 된다.
Python
풀이 코드
def solution(n):
answer = []
def mov(target, now, to, other):
if target == 1:
answer.append([now, to])
return
mov(target - 1, now, other, to)
answer.append([now, to])
mov(target - 1, other, to, now)
mov(n, 1, 3, 2)
return answer해석
Java 풀이와 같다.
여담
Python 초기 풀이가 따로 있는데, 비효율적인 코드이므로 위의 코드를 참고하자.
def solution(n):
answer = []
place = {i: 0 for i in range(0, n)}
field = [(1 << n) - 1, 0, 0]
stack = []
def check(target, now, to):
spot = [now, to]
nxt = set([0, 1, 2]) - set(spot)
for s in spot:
if field[s] % (1 << target):
for i in range(target - 1, -1, -1):
if (field[s] >> i) & 1:
stack.append((i, nxt.pop()))
return False
return True
for h in range(n - 1, -1, -1):
stack.append((h, 2))
while stack:
target, to = stack[-1]
now = place[target]
if check(target, now, to):
field[now] -= 1 << target
field[to] += 1 << target
place[target] = to
del(stack[-1])
answer.append([now + 1, to + 1])
return answer