[Algorithm] [백준] 2251 - 물통 (BFS)

1. a, b, c 세 가지 물병으로 주고 받을 수 있는 경우의 수 구하기

• x -> y
• x -> z
• y -> x
• y -> z
• z -> x
• z -> y

2. 모든 경우의 수를 전부 찾는 완전탐색이다.
3. BFS를 사용한다.

## 백준 2251 물통

import sys
input = sys.stdin.readline

from collections import deque

def visit(x, y):
    if visited[x][y] == 0:
        visited[x][y] = 1
        q.append((x, y))

def BFS():
    while q:
        # x : a물통에 들어있는 물의 양, y : b물통에 들어있는 물의 양, z : c물통에 들어있는 물의 양
        x, y = q.pop()
        z = c - x - y

        # a물통이 비어있을 때 c물통의 양 저장
        if x == 0:
            ans.append(z)

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

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

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

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

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

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


a, b, c = map(int, input().split())

# 경우의 수를 담을 큐 (a, b 물병의 남은 용량 표시)
q = deque()
q.append((0, 0))  # 처음 a, b는 0, 0이다.

# 방문 여부(visited[x][y])
visited = [[0] * (b+1) for _ in range(a+1)]
visited[0][0] = 1

# 답 저장할 배열(c 저장)
ans = []

BFS()

# 답 출력
ans.sort()
for x in ans:
    print(x, end=' ')

• water 을 구하는 방법은 x -> y의 min(x, b-y)로 예를 들어보면,
  x -> y로 옮겨져야 할 물을 구하는 것이다.
  즉, x 전체를 옮기거나 b에서 남은 부분을 채워 b물통을 꽉 채우는 방법이 있는데 그 중 최소값으로 정한다.
  왜냐하면 b물통에 물이 초과되면 안되기 때문이다.

• visit 함수는 옮긴 후의 x와 y 상태를 큐에 저장하기 위한 함수이다.