[Python]백준 12886번 돌 그룹

문제 링크

문제 풀이

1. 총 돌의 개수는 고정이다(3개로 고정입니다)

2. 총 돌의 개수가 3의 배수가 아니라면 어떤 수를 쓰더라도 모든 그룹에 있는 돌의 개수를 같게 만들 수 없다.(이게 포인트!)

풀이과정

먼저 이 문제는 돌의 총합이 3의 배수가 되지 않으면, 어떠한 방식을 써도 모든 그룹에 돌의 개수를 같게 만들어 줄 수 없다.
BFS를 실행하여 두 그룹끼리 돌 개수를 비교하여 큐에 추가하고, 이를 큐가 빌 때까지 반복한다.

만약 돌이 분배된 개수가 이전에 나온 적이 있었다면 해당 코드는 실행하지 않는다. 왜냐하면 똑같은 결과가 반복되어서 나올 것이기 때문이다. (중복 제거)

정답 코드

import sys
input=sys.stdin.readline
from collections import deque

def bfs():    
    global a,b,c,total, visit
    dq=deque()
    dq.append((a,b))
    visit[a][b]=True
    global result
    while dq:
        x,y= dq.popleft()
        z=total-x-y
        if x==y==z:
            print(1)
            return
        for a,b in (x,y), (y,z), (x,z):
            if a<b:
                b-=a
                a+=a
            elif a>b:
                a-=b
                b+=b
            else:
                continue
            c=total-a-b
            x=min(a,b,c)
            y=max(a,b,c)
            if not visit[x][y]:
                dq.append((x,y))
                visit[x][y]=True
    print(0)
a,b,c=map(int, input().split())
result=0
total=a+b+c
visit=[[False] * (total+1) for _ in range(total+1)]

if total % 3 !=0:
    print(0)
else:
    bfs()