백준: 2251 물통

문제

 

2251번: 물통

 

문제 풀이

 A, B, C의 물통이 있고, 처음에는 C의 물통에만 물이 가득차 있다. 물통에 물을 한번에 다른 통으로 이동시키는 경우, A가 비어있는 경우에 C의 물통에 차있는 물의 양을 반환하는 문제이다. 물을 옮길 수 있는 경우의 수는 6가지가 존재한다. 이는 순열로 DFS나 permutaion을 이용해 구해도 되지만, `A → B`, `A → C`, `B → A`, `B → C`, `C → A`, `C → B`와 같은 경우의 수를 하드코딩하여 경우의 수를 분류하였다.

 

 문제를 풀기 위해 BFS를 통해 동일한 경우의 수인지 판단하면서, 물을 옮겻을 때 A가 비는지 확인하면 문제에서 원하는 답을 반환할 수 있다.

 

코드

from sys import stdin
from collections import deque, defaultdict


def bfs(a, b, c):
    q = deque([[a, b, c]])
    check[tuple(q[0])] = True

    while q:
        cur_case = q.popleft()

        if not cur_case[A]:
            answer.append(cur_case[C])

        for rm_water, add_water in cases:
            next_case = cur_case[:]

            if cur_case[rm_water] + cur_case[add_water] > bucket_size[add_water]:
                next_case[rm_water] = \
                    cur_case[rm_water] + cur_case[add_water] - bucket_size[add_water]
                next_case[add_water] = bucket_size[add_water]
            else:
                next_case[add_water] = cur_case[rm_water] + cur_case[add_water]
                next_case[rm_water] = 0

            if not check[tuple(next_case)]:
                check[tuple(next_case)] = True
                q.append(next_case)

if __name__ == '__main__':
    answer = []
    A, C = 0, 2
    cases = ((0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1))
    check = defaultdict(bool)
    bucket_size = list(map(int, stdin.readline().split()))
    bfs(0, 0, bucket_size[C])
    print(*sorted(answer))