백준 2251 물통(BFS)

https://www.acmicpc.net/problem/2251

2251번: 물통

물을 옮길 수 있는 방법은 총 6가지이다.

x -> y, x -> z, y -> x, y -> z, z -> x, z -> y : 6가지

 

https://cijbest.tistory.com/14 그림참고

x -> y 라고 한다면 2가지의 경우가 있을 수 있는데

1. x의 담긴 물을 모두 y로 옮긴다

2. x의 담긴 물을 모두 y로 옮기려고 했지만 y의 용량(b)때문에 b-y만 옮기는 경우

 

1,2 case의 min()값을 옮겨주는 물이라고 생각하고 방문처리를 진행해준다.

why?

max값이라고 하면 애초에 말이 안됨. x-water해줘야되는데 음수가 될 수도 있음

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

 

visited[x][y]에 저장을 하면서 중복을 방지해준다.

ex) x->y에 대해서 x,y 물통에 현재 있는 값을 기억해준다.

visited[x][y] => x에 3L, y에 5L 저장되어있다면

visited[3][5] = 1을 해줌으로써 x=3,y=5일 때의 경우를 고려했다라는 것을 체크한다.

 

import sys
from collections import deque

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

def bfs():

    while q:
        x, y = q.popleft()
        z = c - x - y

        if x == 0:
            answer.append(z)

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

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

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

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

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

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


a, b, c = map(int, sys.stdin.readline().split())

q = deque()
q.append((0, 0))

visited = [[False] * (b+1) for _ in range(a+1)]
visited[0][0] = True

answer = []

bfs()
answer.sort()
for i in answer:
    print(i, end=" ")