백준 12886 파이썬 - 돌 그룹

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

12886번: 돌 그룹

문제

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

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

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

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

코드

import sys
from collections import deque
a, b, c = map(int, sys.stdin.readline().split())
visited = [[False] * 1501 for _ in range(1501)]
total = a + b + c
def bfs(i, j, k):
    q = deque()
    q.append((i, j))
    visited[i][j] = True
    while q:
        x, y = q.popleft()
        z = total - x - y
        if x == y == z:
            return 1
        for nx, ny in ((x, y), (x, z), (y, z)):
            if nx < ny:
                ny -= nx
                nx += nx
            elif nx > ny:
                nx -= ny
                ny += ny
            else:
                continue
            nz = total - nx - ny
            maxN = max(nx, ny, nz)
            minN = min(nx, ny, nz)
            if not visited[maxN][minN]:
                q.append((maxN, minN))
                visited[maxN][minN] = True
    return 0
if total % 3 != 0:
    print(0)
else:
    print(bfs(a, b, c))

풀이

total에서 두 값을 빼면 나머지 값이 나오는 것을 활용해야하고, 수식에서 뺄셈을 먼저 해야만 한다. 두 값이 같으면 나머지 값도 전체합이 같아야 하므로 같아져서 visited를 2차원 배열로 해도 된다. 전체 합이 3으로 안나뉘면 0을 출력하고 나눠지면 bfs를 실행하고 리턴 값인 0 혹은 1을 출력한다. visited를 안해주니 틀리고 덧셈을 먼저하니 답이 안나와 당황했다. 간단한 부분들을 신경써야겠다.