백준 12886 돌그룹 파이썬

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

12886번: 돌 그룹

 

세 그룹이 같은 돌 개수를 가져야 한다. -> 전체 돌 개수가 3의 배수가 아니라면 불가능하다. 

 

(a, b, c) == (a, c, b) == (b, a, c) == (b, c, a) == (c, a, b) == (c, b, a) -> 순서는 상관없다. 

visited[a][b] : (a, b, total - a - b) 방문했다 표시

아래 코드와 같이 (a,b,c)의 경우, 추가적으로 6가지 경우 모두 True이다.

 

def visit(a, b, c):
    global visited
    for x, y in [(a, b), (b, c), (c, a)]:
        visited[x][y] = True
        visited[y][x] = True

 

 

 

import sys
from collections import deque

a, b, c = map(int, sys.stdin.readline().split())
total = a + b + c

if total % 3 != 0:
    print(0)
    sys.exit()

q = deque()
q.append((a, b))
visited = [[False] * (total + 1) for _ in range(total + 1)]


def visit(a, b, c):
    global visited
    for x, y in [(a, b), (b, c), (c, a)]:
        visited[x][y] = True
        visited[y][x] = True


while q:
    a, b = q.popleft()
    c = total - (a + b)
    if a == b and b == c:
        print(1)
        sys.exit()
    for x, y in [(a, b), (b, c), (a, c)]:
        if x > y:
            x -= y
            y += y
        elif y > x:
            y -= x
            x += x
        else:
            continue
        if visited[x][y] is False:
            z = total - (x + y)
            visit(x, y, z)
            q.append((x, y))
print(0)