[BOJ 23240, Python 3] Colorful Tower of Hanoi

https://www.acmicpc.net/problem/23240

23240번: Colorful Tower of Hanoi

 

ICPC 2021 예선전에 나온 문제이다. 내가 맡아서 풀은 문제인데 대회 당시 분명 풀이가 맞지만 다른 예외사항을 찾지 못한 것 같아서 맞왜틀이 나와 결국 풀지 못한채로 끝났다. 지금 다시 풀어보니까 예외 사항 하나를 찾아서 풀었음

대회에서 풀었으면 등수가 거의 (현재 등수) / 2 수준으로 뛰어 올랐을텐데 참 많이 아쉽다.

 

풀이

일단 한 층마다 색깔도 같고, 크기가 같지만, 숫자가 다른 디스크가 여러 개 있는데, 이런 디스크들의 묶음을 하나의 디스크로 치환해서 문제를 풀려고 하면 일반적인 하노이탑 형태가 보이게 된다.

 

그리고 색깔마다 이동횟수가 다르다고 문제에 적혀있는데 자세한 방식을 알아보자.

• 모든 색깔의 디스크들은 한 번 이동할 경우 같은 층의 디스크 번호의 순서가 반대로 뒤집어진다.
• 초록색(G)은 이동후의 순서가 중요하지 않으므로 한 번 이동으로 끝낼 수 있다.
• 파란색(B)은 현재까지 이동한 횟수가 홀수인 경우엔 한 번만 3번 고리로 이동하면 끝나지만, 현재까지 이동한 횟수가 짝수인 경우에는 1번 고리나 2번 고리에 존재할 것이다. 그러면 1번 고리에 있으면 2번 고리로, 2번 고리에 있으면 1번 고리로 이동시킨 뒤 3번 고리로 이동 해야한다. 그러면 B는 조건을 충족한 채로 3번 고리로 이동할 수 있게 된다.
• 빨간색(R)은 파란색과 비슷하게 이동한 횟수가 짝수인 경우엔 한 번만 3번 고리로 이동하면 끝나지만, 홀수인 경우에는 이동을 최소 한 번 했으므로 1번 고리나 2번 고리에 존재할 것이다. 그러면 1번, 2번 고리중 이동할 수 있는 고리로 이동시킨 뒤 3번 고리로 이동해야한다. 그러면 R은 조건을 충족한 채로 3번 고리로 이동할 수 있게 된다.

나머지는 일반 하노이탑 형식대로 이동하면 된다.

 

예제 1번을 살펴보자

1. B 3을 이동해야 하는데, 현재 B의 이동횟수가 0번이므로 2번 고리로 이동 후 3번 고리로 이동해야 한다.
   • R을 1번 고리에서 3번 고리로 이동함(총 이동 횟수 1회)
   • B를 1번 고리에서 2번 고리로 이동함(총 이동 횟수 4회)
   • R을 3번 고리에서 1번 고리로 이동함(총 이동 횟수 5회)
   • B를 2번 고리에서 3번 고리로 이동함(총 이동 횟수 8회)
2. 이제 1번 고리에 있는 R을 3번 고리로 이동해야 하는데, R의 이동 횟수가 2회이므로 짝수이니 바로 3번 고리로 이동시켜주면 된다.(총 이동 횟수 9회)

 

예제 2번도 살펴보자. 여기서는 각 층마다 기록횟수를 저장해둘 것이다.

1. R 3을 이동해야 하는데, 현재 R의 이동횟수가 0번이므로 바로 3번 고리로 이동하면 된다.
   • G 1의 이동 횟수 2회
   • B 2의 이동 횟수 1회
   • R 3의 이동 횟수 1회
   • 총 이동 횟수는 (1 * 2) + (2 * 1) + (3 * 1) = 7회
2. B 2를 이동해야 하는데, B 2의 이동횟수가 1회이므로 홀수이니 바로 3번 고리로 이동해줄 수 있다.
   • G 1의 이동 횟수 1회
   • B 2의 이동 횟수 1회
   • 총 이동 횟수는 7 + (1 * 1) + (2 * 1) = 10회
3. G 1을 이동해야 하는데, 이건 순서가 상관없으므로 바로 3번 고리로 이동해줄 수 있다.
   • G 1의 이동 횟수 1회
   • 총 이동 횟수는 10 + (1 * 1) = 11회

 

이렇게 하면 예제 3번도 짧게 바로 구할 수 있게 된다.

 

 

이제 여기에 예외사항이 두 가지가 존재한다.

1. 한 층에 디스크가 1개 있을 경우
   이 부분은 색깔과 관계 없이 바로 3번 고리로 이동해주면 된다.
2. 맨 위에 있는 층의 디스크들에 대한 이동 횟수 처리
   맨 윗층의 디스크의 색깔이 G인 경우엔 순서를 고려하지 않으므로 바로 3번 고리로 넘겨주면 되지만, 색깔이 파란색이나 빨간색인 경우에는 각각 짝수일 때, 홀수일 때 두 번씩 움직여야 한다.
   두 번씩 움직여야할 때는 다른 층에서 두 번 움직일 때처럼 (디스크의 갯수) * 2회만큼 움직이는게 아니라 (디스크의 갯수) * 2 - 1회만큼 움직이면 된다.
   왜냐하면 맨 아래에 둘 디스크는 두 번 움직일 필요없이 3번 고리로 넘겨주면 되기 때문이다.

 

그래서 이 예외사항까지 잘 처리하면 문제를 풀 수 있게 된다.

대회에서 예외사항 2번을 생각지도 못했는데, 팀원들한테 좀 더 자세히 알려주고 대회 끝나기 전까지 여기에 시간을 투자했어야 했는지 여러가지 생각이 든다.

 

 

코드

코드가 원래 C++ 코드를 그대로 가져온거라 줄일 수 있는 부분이 많이 남아 있습니다.

m = int(input())
arr = [input().split() for i in range(m)]
color = [] # 색깔을 저장한 배열
val = [] # 한 층에 디스크가 몇 개 있는지 저장한 배열
move = [0] * m # 한 층의 이동 횟수
ans = 0
for i in range(m):
    color.append(arr[i][0])
    val.append(int(arr[i][1]))
for i in range(m-1, -1, -1):
    if color[i] == 'G':
        move[i] += 1
        for j in range(i-1, -1, -1):
            move[j] += 2 ** (i - j - 1)
    elif color[i] == 'B': # 현재 move가 짝수인 경우 두 번 이동해야함. 홀수면 한 번 이동해야함
        if move[i] % 2 == 0 and val[i] != 1: # 예외사항 1번 처리
            if i == 0: ans -= 1 # 예외사항 2번 처리
            move[i] += 2
            for j in range(i-1, -1, -1):
                move[j] += 2 ** (i - j)
        else:
            move[i] += 1
            for j in range(i-1, -1, -1):
                move[j] += 2 ** (i - j - 1)
    else: # 현재 move가 짝수인 경우 한 번 이동해야함. 홀수면 두 번 이동해야함
        if move[i] % 2 == 0 or val[i] == 1: # 예외사항 1번 처리
            move[i] += 1
            for j in range(i-1, -1, -1):
                move[j] += 2 ** (i - j - 1)
        else:
            if i == 0: ans -= 1 # 예외사항 2번 처리
            move[i] += 2
            for j in range(i-1, -1, -1):
                move[j] += 2 ** (i - j)
 
for i in range(m):
    ans += val[i] * move[i]
 
print(ans)