[백준] 12886번: 돌 그룹

문제

백준 - 12886번: 돌 그룹

분석

세 개의 돌 그룹 a, b, c가 주어졌을 때 모든 돌 그룹의 개수를 같게 만들 수 있으면 1, 없으면 0을 출력하는 문제이다.
단계별 움직임:
크기가 다른 두 돌 그룹을 선택해서 작은 것이 x, 큰 것이 y라 할 때 x는 x+x로, y는 y-x로 만든다.

a, b, c의 상태를 모두 고려한 3차원 visited배열을 이용하다가 실패했다.

가장 작은 것과 큰 것만 가지면 a,b,c 총합을 이용해서 가운데 값을 따로 고려하지 않아도 된다.
(visited배열을 2차원으로 만들 수 있다.)
큐에는 가장 작은 값과 가장 큰 값을 세트로 가져가고 그 둘의 상태를 보고 방문여부를 결정한다.
total(총합)을 이용해서 나머지 하나(z)를 구하고 그 세 그룹의 조합을 모두 고려해서 bfs를 진행한다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

from collections import deque
lst = sorted(list(map(int, input().split())))
total = sum(lst)
a, b = lst[0], lst[2]
visited = [[False]*(total+1) for _ in range(total+1)]

def bfs(a, b):
    q = deque([(a, b)])
    visited[a][b] = True
    while q:
        x, y = q.popleft()
        z = total-x-y
        if x == y == z:
            return 1
        for a, b in [(x,y), (x, z), (y,z)]:
            if a != b:
                if a > b: a, b = b, a
                lst = sorted([a + a, b - a, total-(a+a)-(b-a)])
                a, b = lst[0], lst[2]
                if not visited[a][b]:
                    visited[a][b] = True
                    q.append((a, b))
    return 0

print(bfs(a, b))

끝으로..

총합을 이용하여 메모리를 아낄 수 있는 문제였다. 이런 사고를 할 수 있는 유연함이 생겼으면 한다.