💡 문제
오늘은 새로운 하노이 탑 게임을 해보려고 한다. 이 게임의 규칙은 다음과 같다.
- 막대는 총 세 가지 종류가 있다. 막대 A, 막대 B, 막대 C
- 게임이 시작될 때, 각각의 막대에는 0개 또는 그 이상의 원판이 놓여져 있다.
- 모든 원판의 크기는 같으며, 원판의 종류도 A, B, C로 세 가지가 있다. 원판은 원판 A, 원판 B, 원판 C와 같이 표현한다.
- 한 번 움직이는 것은 한 막대의 가장 위에 있는 원판을 다른 막대의 가장 위로 옮기는 것이다.
- 게임의 목표는 막대 A에는 원판 A만, 막대 B는 원판 B만, 막대 C는 원판 C만 놓여져 있어야 한다.
- 되도록 최소로 움직여야 한다.
막대 A, 막대 B, 막대 C에 놓여져 있는 원판의 상태가 주어졌을 때, 게임의 목표를 달성하는데 필요한 움직임의 최소 횟수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 막대 A에 놓여져 있는 원판의 개수와 막대 A의 상태, 둘째 줄에 막대 B에 놓여져 있는 원판의 개수와 막대 B의 상태, 셋째 줄에 막대 C에 놓여져 있는 원판의 개수와 막대 C의 상태가 주어진다. 막대의 상태는 밑에 있는 원판부터 주어진다.
각 막대의 상태는 A, B, C로만 이루어진 문자열이며, 모든 막대에 놓여져 있는 원판 개수의 합은 1보다 크거나 같고, 10보다 작거나 같다.
출력
게임의 목표를 달성하는데 필요한 움직임의 최소 횟수를 출력한다.
💭 접근
이 문제는 BFS를 사용하여 간단하게 해결할 수 있다.
다만 입력으로 주어지는 막대의 상태를 저장할 때 해당 막대에 원판이 하나도 없는 경우 따로 원판에 대해 입력이 없기 때문에 해당 막대의 원판의 개수가 0인 경우는 ''를 저장하고 아닌 경우에 입력으로 주어지는 원판의 상태를 저장하면 된다.
s = []
for _ in range(3):
disc = list(input().split())
if disc[0] == '0':
s.append('')
else:
s.append(disc[1])이제 bfs() 함수를 보자.
def bfs():
q = deque()
q.append([s[:], 0])
visited.add(s[0] + ' ' + s[1] + ' ' + s[2])
while q:
sticks, cnt = q.popleft()
if check(sticks[0], sticks[1], sticks[2]):
return cnt
for curr in range(3):
if len(sticks[curr]) == 0:
continue
for next in range(3):
if curr != next:
n_sticks = sticks[:]
n_sticks[next] += n_sticks[curr][-1]
n_sticks[curr] = n_sticks[curr][:len(n_sticks[curr]) - 1]
v = n_sticks[0] + ' ' + n_sticks[1] + ' ' + n_sticks[2]
if v not in visited:
visited.add(v)
q.append([n_sticks[:], cnt + 1])여기선 간단하게 막대 3개를 순회하며 동일한 막대에서 움직이는 경우를 제외하고 다른 막대로 옮길 수 있는 경우만 확인한다.
이때 3개의 막대의 상태가 중복되지 않도록 방문 처리를 하는 visited를 set() 자료형으로 선언하여 중복 체크를 해주면 된다.
📒 코드
from collections import deque
def bfs():
q = deque()
q.append([s[:], 0])
visited.add(s[0] + ' ' + s[1] + ' ' + s[2])
while q:
sticks, cnt = q.popleft()
if check(sticks[0], sticks[1], sticks[2]):
return cnt
for curr in range(3):
if len(sticks[curr]) == 0:
continue
for next in range(3):
if curr != next:
n_sticks = sticks[:]
n_sticks[next] += n_sticks[curr][-1]
n_sticks[curr] = n_sticks[curr][:len(n_sticks[curr]) - 1]
v = n_sticks[0] + ' ' + n_sticks[1] + ' ' + n_sticks[2]
if v not in visited:
visited.add(v)
q.append([n_sticks[:], cnt + 1])
def check(a, b, c):
if 'B' not in a and 'C' not in a:
if 'A' not in b and 'C' not in b:
if 'A' not in c and 'B' not in c:
return True
return False
s = []
for _ in range(3):
disc = list(input().split())
if disc[0] == '0':
s.append('')
else:
s.append(disc[1])
visited = set()
print(bfs())💭 후기
오랜만에 간단한 BFS 문제였다.
🔗 문제 출처
https://www.acmicpc.net/problem/12906
