[백준] 12886 돌 그룹

문제

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

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

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

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

입력

첫째 줄에 A, B, C가 주어진다. (1 ≤ A, B, C ≤ 500)

출력

돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력한다.

내 풀이

from collections import deque

a, b, c = map(int, input().split())
total = a + b + c

if total%3 != 0:
    print(0)
    exit()
    
visited = set()
q = deque()

def add_state(x, y):
    z = total - x - y
    sorted_state = tuple(sorted([x, y, z]))
    if sorted_state not in visited:
        visited.add(sorted_state)
        q.append(sorted_state)
        
start = tuple(sorted([a, b, c]))
visited.add(start)
q.append(start)

while q:
    x, y, z = q.popleft()
    if x == y == z:
        print(1)
        break
    
    for u, v in ((x, y), (x, z), (y, z)):
        if u != v:
            if u < v:
                add_state(u+u, v-u)
            else:
                add_state(u-v, v+v)
else:   # while-else
    print(0)

시간 복잡도 → $O(N)$
각 상태에서 새로운 상태로 최대 n번 이동
공간 복잡도 → $O(N)$
$\because$ visited 배열 사용 (방문한 튜플 저장)

코멘트

처음에는 그래프 탐색인 줄 모르고 문제를 곧이 곧대로 풀었다가 시간 초과의 철퇴를 맞았다. 그러나 이 문제는 BFS나 DFS를 이용해 탐색을 하다가 a, b, c가 모두 같아질 때를 찾아야 한다. 돌을 같은 개수로 만들 수 없을 때는 1) 돌의 총 개수가 3의 배수가 아닐 때 2) 규칙에 맞게 돌을 움직여도 돌의 개수가 모두 같아지지 않을 때이므로 이 때는 0을 출력하도록 한다.

이 풀이에서는 BFS를 채택하여 queue에 각 (a, b, c) 튜플을 넣었다 빼면서 돌을 이동시키고 조건을 만족하면 while문을 종료하도록 한다. visited 배열이 필요한 이유는 돌을 움직이는 중간 과정에서 이전과 동일한 조합을 피하면서 효율적으로 탐색하기 위함이다.

[백준] 12886 돌 그룹

문제

입력

출력

내 풀이

코멘트

References