문제

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.

강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.

크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.

A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.

# 12886
import sys
input = lambda: sys.stdin.readline().strip()

from collections import deque

# 1. 1그룹 - 2그룹, 2그룹 - 3그룹, 3그룹 - 1그룹 
# 2. 3차원 list를 통해 값을 확인하면 범위가 너무 커짐
# 3. set을 통해 값 확인해 범위 축소

a, b, c = map(int, input().split())

def bfs():
    global a, b, c
    size = a + b + c
    
    if size % 3 != 0:
        return 0
    
    queue = deque()
    queue.append((a, b, c))
    
    stone = set()
    stone.add((a, b, c))
    
    while queue:
        x, y, z = queue.popleft()
        
        if x == y == z:
            return 1
        
        # 1 - 2
        if x > y: 
            if 2*y < size and (x-y, 2*y, z) not in stone:
                stone.add((x-y, 2*y, z))
                queue.append((x-y, 2*y, z))
        else:
            if 2*x < size and (2*x, y-x, z) not in stone:
                stone.add((2*x, y-x, z))
                queue.append((2*x, y-x, z))
                
        # 2 - 3
        if y > z:
            if 2*z < size and (x, y-z, 2*z) not in stone:
                stone.add((x, y-z, 2*z))
                queue.append((x, y-z, 2*z))
        else:
            if 2*y < size and (x, 2*y, z-y) not in stone:
                stone.add((x, 2*y, z-y))
                queue.append((x, 2*y, z-y))
                
        # 3 - 1
        if z > x:
            if 2*x < size and (2*x, y, z-x) not in stone:
                stone.add((2*x, y, z-x))
                queue.append((2*x, y, z-x))
        else:
            if 2*z <= size and (x-z, y, 2*z) not in stone:
                stone.add((x-z, y, 2*z))
                queue.append((x-z, y, 2*z))
                
    return 0

print(bfs())            

백준 12886 돌 그룹