2251. 물통 (Python)

 

2251번: 물통

 

풀이

 BFS를 통해서 from 물통에서 to 물통으로 물을 쏟아 부은 후 A 물통과 C 물통의 물의 양을 살펴본다. 큐에는 리스트의 형태로 '[A 물통의 물의 양, B 물통의 물의 양, C 물통의 물의 양]'으로 값을 넣어 줬다.

 

 큐에 중복된 경우를 넣지 않게 하기 위해 물의 양들을 문자열로 만들고 이를 딕셔너리의 키로 사용하여 체크해줬다. 예를 들어 A, B, C에 각각 4, 3, 22 리터의 물이 들어있다면 문자열로 '4 3 22'와 같이 중간에 빈 문자를 삽입하여 문자열을 만들어주고 딕셔너리에 해당 문자열을 키로 하는 값이 있는지를 체크한다.

# 각 물통의 물의 양으로 방문 체크 딕셔너리에서 키로 사용될 문자열 생성
def setKey(arr):
    return str(arr[0]) + " " + str(arr[1]) + " " + str(arr[2])

 

 위와 같은 방법으로 중복되는 경우를 제외하고 BFS를 통해서 문제의 답을 구할 수 있다.

 

코드

from collections import deque
from collections import defaultdict
from copy import deepcopy


# 각 물통의 물의 양으로 방문 체크 딕셔너리에서 키로 사용될 문자열 생성
def setKey(arr):
    return str(arr[0]) + " " + str(arr[1]) + " " + str(arr[2])


# from 물통에서 to 물통으로 물을 쏟아 붓는 함수
# from 물통 번호, to 물통 번호, from 물통에 들어있는 물의 양, to 물통에 들어있는 물의 양
# return 값 : 물을 부은 후 from 물통의 물의 양, to 물통의 물의 양
def pourWater(toBucket, fromLiter, toLiter):
    toMaxLiter = buckets[toBucket]  # to 물통의 부피
    toRemain = toMaxLiter - toLiter  # to 물통의 남은 부피

    # to 물통의 남은 부피가 from 물통의 물의 양 이하일 때는 물을 쏟아 부으면
    # from 물통에는 to 물통의 남은 부피만큼의 물이 사라지고 to 물통은 가득 차게 된다.
    if toRemain <= fromLiter:
        return fromLiter - toRemain, toMaxLiter
    else:  # 반대의 경우는 from 물통의 물이 모두 to 물통으로 옮겨진다.
        return 0, toLiter + fromLiter


if __name__ == '__main__':
    buckets = list(map(int, input().split()))
    q = deque()
    res = set()  # A 물통의 물의 양이 0일 때, C 물통의 물의 양 -> 중복을 피하기 위해 셋으로 받는다.
    visitedDict = defaultdict(bool)  # 방문 체크 딕셔너리

    q.append([0, 0, buckets[2]])  # (A 물통의 물의 양, B 물통의 물의 양, C 물통의 물의 양)
    visitedDict[setKey([0, 0, buckets[2]])] = True

    while q:
        nowBuckets = q.popleft()

        if nowBuckets[0] == 0:  # A 물통의 물의 양이 0이면 res에 C 물통의 물의 양을 기록
            res.add(nowBuckets[2])

        for i in range(3):  # from 물통 번호
            if nowBuckets[i] == 0:  # from 물통이 비어 있으면 탐색하지 않음
                continue

            for j in range(3):  # to 물통 번호
                if i == j:  # 두 물통이 같은 경우는 continue
                    continue

                tmpBuckets = deepcopy(nowBuckets)  # 각 물통의 물의 양을 기록하는 임시 리스트
                fromBucket, toBucket = pourWater(j, nowBuckets[i], nowBuckets[j])  # 물을 부은 후 남은 물의 양
                tmpBuckets[i], tmpBuckets[j] = fromBucket, toBucket  # tmpBuckets에 바뀐 물의 양 기록
                dictKey = setKey(tmpBuckets)  # 바뀐 물의 양을 기준으로 key 생성

                if not visitedDict[dictKey]:  # 이전에 체크하지 않은 경우 큐에 넣어주고 방문 체크
                    q.append(tmpBuckets)
                    visitedDict[dictKey] = True

    resList = sorted(list(res))
    print(*resList)