[2251] 물통 in python

 

문제 이해를 못해서

한참 헤맸던 문제 ㅠ..ㅠ

 

부피가 A,B,C 리터인 물통 3개가 있다.

처음에는 C 리터인 물통만 가득 채워져있다.

물을 옮길땐 조건이 있다.

한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다.

 

사실 위 문장을 제대로 파악하지 않고 넘어가서

정말 헤맸던 문제다.

 

예시를 들어서 설명해보면

8,9,10 리터인 물통 3개가 있다고 가정한다.

C물통에서 A물통으로 물을 옮기려면

A물통을 가득채우거나

또는 C물통이 빌때까지 부어야하는데

A물통이 C물통보다 용량이 작으므로

이때는 C물통에서 A물통으로 8리터를 옮긴다.

그러면 C리터에는 2리터의 물만이 남게 된다.

 

만약 B물통에 5리터, C 3리터가 남아있다고 가정한다.

B물통를 가득채우려면 4리터가 필요하다.

그러나 C물통에는 3리터만 있다.

따라서 이때는 B물통에 3리터를 모두 붓고

C물통을 완전히 비우는 방법을 써야한다.

 

 

visited를 쓰지 않으면

무한 루프에 걸린다..

 

그래서 써주어야하는데

처음에는 c->a --> a->b, a->c, ---> 

이런식으로 손으로 직접 써봤는데

방문처리 없으면 무한반복이다 ^^

 

그래서 visited[a][b] 이런식으로 

이중리스트를 사용하여

a물통, b물통에 각각 얼마씩 있을때를 계산했는지

안했는지를 판단하기 위해 방문처리를 해준다.

 

 

 

 

from collections import deque

a, b, c = map(int, input().split())
MAX = c
queue = deque()
visited = [[False] * (b + 1) for _ in range(a + 1)]
answer = []


def pour(x, y):
    if not visited[x][y]:
        visited[x][y] = True
        queue.append((x, y))


def bfs():
    queue.append((0, 0))  # a=0, b=0 : 초기상태
    visited[0][0] = True  # a=0이고 b=0일때는 이미 계산했었으니 안해도 되도록 방문처리
    while queue:
        x, y = queue.popleft()
        z = c - x - y  # c 물통에 현재 남아있는 물의 양
        if x == 0:
            answer.append(z)
        # x -> y
        water=min(x,b-y)
        pour(x-water,y+water)
        # x->y로 옮길때 a통에 있는 물의 양 x가 작은지
        # b통에 들어갈 수 있는 물의 양 b-y값이 작은지 판별 후
        # 작은 값을 water에 넣어준다.
        # 물을 넘치게 할 수 없으니까 , a통에 있는 물의 양이 b통에 들어갈 수 있다면?
        # x값이 b-y값보다 작은 것이다.

        # x-> z
        water=min(x,c-z)
        pour(x-water,y)

        # y-> x
        water=min(y,a-x)
        pour(x+water,y-water)

        # y-> z
        water=min(y,c-z)
        pour(x,y-water)

        # z-> x
        water=min(z, a-x)
        pour(x+water,y)

        # z-> y
        water=min(z,b-y)
        pour(x,y+water)



bfs()
print(*sorted(answer))