[백준/Python] 2251 물통

문제 링크

2251번: 물통

 

문제 풀이

• 물을 옮기는 경우는 A에서 B, C로, B에서 A, C로, C에서 A, B로 총 6가지가 존재한다.
• A에서 B로 물을 옮긴다고 한다면, 현재 A에 들어있는 물의 양과 B의 컵의 양에서 들어있는 물의 양을 뺀 만큼의 양 중에서 더 작은 값만큼 옮겨지게 된다.
• 물을 옮긴 후에 현재 각 컵에 들어있는 물의 양이 전에도 나왔던 값인지를 비교한 후, 나오지 않았다면 큐에 추가한다.
• 위 과정을 큐가 비어있을 때까지 반복한다.

 

전체 코드

import sys
from collections import deque

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

def bfs():
    while queue:
        x, y, z = queue.popleft()
        if x == 0:
            res.append(z)
        # x -> y
        water = min(x, b-y)
        move(x-water, y+water, z)
        # x -> z
        water = min(x, c-z)
        move(x-water, y, z+water)
        # y -> x
        water = min(a-x, y)
        move(x+water, y-water, z)
        # y -> z
        water = min(y, c-z)
        move(x, y-water, z+water)
        # z -> x
        water = min(a-x, z)
        move(x+water, y, z-water)
        # z -> y
        water = min(b-y, z)
        move(x, y+water, z-water)

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

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

queue = deque()
queue.append((0, 0, c))
visited[0][0] = True

bfs()

res.sort()
for x in res:
    print(x, end=" ")