[백준] 2251번 물통 (python)

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

2251번: 물통

 

물통이 3개로 고정되어 있고 물을 옮길 수 있는 경우 역시 고정되어 있었기 때문에 고려해야 할 경우의 수가 정해져 있다고 생각했다. A가 비어있을 때 C에 들어있는 물의 양을 찾고자 했다. 하지만 이 문제를 어떻게 탐색으로 풀어야 할지 모르겠어서 답안을 참고했다. 이 문제는 완전탐색(BFS)을 통해 고려한 경우의 수는 하나씩 제외시키면서 풀어야 한다. 고려한 방식을 제외시키는 이유는, 같은 경우를 계속해서 고려해 무한루프에 빠지는 것을 막기 위해서다.

 

정리하면 아래와 같다.

먼저 물통은 A, B, C, 3개로 고정되어 있으며, 물은 다른 물통이 가득 차도록 옮겨야 한다.

A, B, C가 갖고 있는 물의 양은 x, y, z로 가정한다.

1. 경우의 수를 고려하면 총 6가지이다.
   • C ➡️ A
   • C ➡️ B
   • A ➡️ B
   • A ➡️ C
   • B ➡️ A
   • B ➡️ C
2. 이때 물을 옮기는 특정 경우의 수를 고려하면 해당 경우의 수는 이제 사용하지 않을 것이다.
   • 무조건 C 물통에만 물이 들어있는 상태로 시작하기 때문에 처음에는 C ➡️ A 또는 C ➡️ B로 물을 옮겨야 한다.
   • 이후 A 또는 B 물통으로 옮겨진 물을 다른 물통으로 옮길 것이다.
   • 이때 1. 물을 넘겨받을 물통에 물이 어느 정도 들어있는지와 2. 넘겨받을 물의 양을 비교해야 한다. (물이 넘치면 안 되기 때문)
     • ex) 물을 9만큼 받을 수 있는 B 물통에 3만큼의 물이 들어있는데, A 물통에서 B 물통으로 7 이상의 물을 주면 B 물통의 물이 넘친다.
   • B가 받을 수 있는 물의 양을 식으로 나타내면 water = min(A, B-y)와 같다.
   • 이렇게 물의 양을 고려하고 경우의 수를 하나씩 제외시키면서 A 물통이 빌 때까지 물을 옮긴다.
3. 이렇게 물을 옮기면서 알 수 있는 것은, A 물통과 B 물통이 갖고 있는 물의 양으로 C 물통이 갖게 되는 물의 양이 정해진다.
   • 이를 식으로 나타내면 z = C - (x + y) 
   • C 물통의 양은 처음에 주어지는 물의 양과 동일하기 때문에 위와 같은 식으로 나타낼 수 있다.
4. 조건문으로 물의 양을 검사하고, 물을 옮기면서 A가 빈 물통이 되는 경우 C에 들어있는 물의 양을 답으로 추가한다.

 

처음에 위 과정은 바로 이해했지만, 코드는 이해를 못했다.

 

A에서 B로 물을 옮기는 과정에서 두 물통이 갖는 물의 양이 변하는 것이기 때문에 (x+water, y-water)는 이해했다. 하지만 C에서 B로 물을 옮길 때 왜 (c-water, x+water)이 아니라 (y, x+water)인지 이해를 못 했다. 하지만 이 부분은 내가 멍청했다..!!! 위에 적어둔 3번 설명을 읽으면 알 수 있듯이, C가 갖고 있는 물의 양은 A와 B가 갖고 있는 물의 양으로 결정된다. 때문에 경우의 수를 체크할 때 C 대신 A와 B가 갖고 있는 물의 양으로 체크하는 것이다.

 

 

정답 코드

import sys
from collections import deque
input = sys.stdin.readline

# 1. 물통 A, B, C가 있는데 C는 이미 가득 차있음. A, B는 비어있음
# 2. 물통에 들어있는 물은 마음대로 옮길 수 이씀
# 3. 최종적으로, A의 물통이 비어있을 때 C 안에 담겨있을 수 있는 물의 양을 구하자

# A물통이 비어있을 때 C물통의 양을 구하자 -> 완전탐색 필요 BFS

def check_visited(x, y):
    global visited
    if not visited[x][y]:
        visited[x][y] = True
        dq.append((x, y))

def bfs():
    dq.append((0, 0))
    visited[0][0] = True
    
    while dq:
        x, y = dq.popleft()
        z = C - x - y # C 잔여량은 A와 B의 물량으로 결정됨!!! 이때 A는 빈 물통이여야 result

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

        if x > 0 and y < B:
            water = min(x, B-y)
            check_visited(x-water, y+water) # A에 담겨있던 물을 B로 이동

        if x > 0 and z < C:
            water = min(x, C-z)
            check_visited(x-water, y)

        if y > 0 and x < A:
            water = min(y, A-x)
            check_visited(x+water, y-water)

        if y > 0 and z < C:
            water = min(y, C-z)
            check_visited(x, y-water)

        if z > 0 and x < A:
            water = min(z, A-x)
            check_visited(x+water, y)

        if z > 0 and y < B:
            water = min(z, B-y)
            check_visited(x, y+water)


A, B, C = map(int, input().split())
visited = [[False] * (B+1) for _ in range(A+1)]
result = []

dq = deque()
bfs()

result.sort()
print(*result)