[골드 4] 백준 12886 - 돌 그룹 (파이썬)

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

풀이

• 돌이 A, B, C 그룹에 있다.
• 한번의 연산이 진행된다.
  • 돌 수가 다른 두 그룹을 골라서, 돌 수가 적은 쪽을 2배로 만들고
  • 많은 쪽에서는 그 차이만큼 뺀다.
• 세 그룹의 돌 수를 모두 같게 만들수 있는가?

if S % 3 != 0:
    print(0)

총합이 3의 배수가 아니라면 절대 세 그룹을 같은 수로 만들 수 없다.

visit = [[False] * S for _ in range(S)]

visit[a][b]가 True이면 (a, b, c = S - a - b)상태를 이미 방문 했다는 의미,

a와 b만 알면 c는 S - a - b로 자동 결정되기 때문에 2차원 배열만 사용한다.

queue = deque()
queue.append((A, B))
visit[A][B] = True

초기 상태를 삽입하고 BFS 탐색을 시작한다.

while len(queue) != 0:
    a, b = queue.popleft()
    c = S - a - b

현재 상태를 꺼내고, 세 그룹의 상태를 a, b, c로 만든다.

D = [a, b, c]
for i in range(3):
    x, y = D[i], D[(i + 1) % 3]

모든 쌍에 대해서 연산을 시도한다. (a, b), (b, c), (c, a) 모든 쌍을 확인한다.

if x == y:
    continue
if x > y:
    x, y = y, x
if not visit[x + x][y - x]:
    queue.append((x + x, y - x))
    visit[x + x][y - x] = True

두그룹의 돌 개수가 같으면 의미 없는 연산이므로 패스하고, x가 항상 더 작은 값이 되도록 정렬한다.

작은 쪽은 2개로 커지고, 큰 쪽은 그 차이만큼 줄어든다.

만들어진 새로운 상태 (x + x, y - x)를 방문한 적 없으면 큐에 추가한다.

if visit[S // 3][S // 3]:
    print(1)
else:
    print(0)

(S // 3, S // 3) 상태에 도달할 수 있으면, 세 그룹이 모두 S / 3 개가 된것이다.

코드

# 백준 12886 - 돌 그룹
# 분류 : BFS

from collections import deque

A, B, C = map(int, input().split())
S = A + B + C

if S % 3 != 0 :
    print(0)
else :
    visit = [[False] * S for _ in range(S)] # S * S

    queue = deque()
    queue.append((A, B))
    visit[A][B] = True

    while len(queue) != 0 :
        a, b = queue.popleft()
        c = S - a - b

        D = [a, b, c]
        for i in range(3) :
            x, y = D[i], D[(i + 1) % 3]

            if x == y :
                continue
            if x > y :
                x, y = y, x
            if not visit[x + x][y - x] :
                queue.append((x + x, y - x))
                visit[x + x][y - x] = True
    
    if visit[S // 3][S // 3] :
        print(1)
    else :
        print(0)