💡 문제
오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.
강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.
크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.
A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 A, B, C가 주어진다. (1 ≤ A, B, C ≤ 500)
출력
돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력한다.
💭 접근
처음 이 문제를 접했을 때 방문처리를 위해 visited 리스트를 3차원으로 저장할 수 있도록 구현하였지만 메모리초과가 발생하였다. 이를 해결하기 위해 고민하던 중, 이 문제를 해결하기 위해선 A, B, C 각각의 상태는 중요하지 않고, 어떤 숫자 조합으로 구성되어있는지만 고려하면 된다는 것을 떠올렸고, visited 리스트를 가장 큰 수, 가장 작은 수의 상태만 저장할 수 있도록 구현하였다. (나머지 숫자는 전체에서 이 둘을 뺀 값이기 때문이다.)
따라서 bfs 함수를 살펴보면 아래와 같다.
nc = sum_abc - (na + nb)
b_num = max(na, nb, nc)
s_num = min(na, nb, nc)
if not visited[b_num][s_num]:
visited[b_num][s_num] = True
q.append((b_num, s_num))위 코드를 보면 돌 두개를 골라 큰 수를 빼고 작은 수를 더하는 과정을 거친 뒤, 전체에서 이 두 수를 빼 나머지 숫자를 구한다. 이후, 가장 큰 수와 가장 작은 수를 구한 뒤 이 두 숫자에 대해서만 방문처리를 해 주었다.
📒 코드
import sys
from collections import deque
def bfs(a, b, c):
q = deque()
q.append((a, b))
visited[a][b] = True
while q:
a, b = q.popleft()
c = sum_abc - (a + b)
if a == b == c:
print(1)
sys.exit()
for na, nb in ([a, b], [a, c], [b, c]):
if na == nb: continue
elif na < nb:
nb -= na
na += na
elif na > nb:
na -= nb
nb += nb
nc = sum_abc - (na + nb)
b_num = max(na, nb, nc)
s_num = min(na, nb, nc)
if not visited[b_num][s_num]:
visited[b_num][s_num] = True
q.append((b_num, s_num))
a, b, c = map(int, input().split())
sum_abc = a + b + c
visited = [[False for _ in range(sum_abc - 1)] for _ in range(sum_abc - 1)]
if sum_abc % 3 != 0:
print(0)
else:
bfs(a, b, c)
print(0)💭 후기
방문처리를 하기 위한 리스트를 1차원이 아닌 고차원 리스트로 활용할 수 있다는 것을 배울 수 있었다.
🔗 문제 출처
https://www.acmicpc.net/problem/12886
