[백준 2251 🥇] 물통

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

2251번: 물통

문제 풀이

• BFS를 이용하면 간단하게 풀 수 있는 문제다.
• 한 물통에서 다른 물통으로 물을 옮길 수 있는 경우는 아래 6가지이다.
  • 1번 물통 -> 2번 물통
  • 1번 물통 -> 2번 물통
  • 2번 물통 -> 1번 물통
  • 2번 물통 -> 3번 물통
  • 3번 물통 -> 1번 물통
  • 3번 물통 -> 2번 물통
• 물을 주는 물통의 물이 다 비워지거나, 물을 받는 물통이 꽉 채워질 때까지 부어야 한다.
• BFS 탐색을 위해서 초기 값으로 앞에 두 물통은 비워져 있고, 세 번째 물통만 꽉 채워져 있는 경우인 (0,0,C)를 큐에 넣어줬다.
• 그리고 visited를 set 자료형으로 선언해서 요소를 추가해서 방문 처리하고,  방문 여부를 확인하기 위해 in 연산자를 사용할 때 상수 시간 내에 가능하도록 했다. 
  • 문제를 풀고 나서 모범 답안 코드를 찾아보니 visited[A][B][C]에 True/False를 표시하는 방법도 있었다!
• while queue를 돌면서 현재 물통의 상태를 pop하고, 위에 적어둔 물을 옮길 수 있는 각 경우에 대해 계산한다.
• 예를 들어 1번 물통의 물을 2번 물통으로 붓는 경우, 1번 물통의 물과 2번 물통의 물을 합쳤을 때 2번 물통의 용량 B보다 커지면, 1번 물통의 모든 물을 비울 수는 없다. 그래서 2번 물통에 부울 수 있는 만큼만 붓고, 나머지는 1번 물통에 남는다.
  • (1번 물통의 물 + 2번 물통의 물 - B)
• 또, 1번 물통의 모든 물을 부울 수 있는 경우엔 1번 물통의 물의 양은 0이 되고, 2번 물통은 (1번 물통 물의 양 + 2번 물통 물의 양)이 된다. 
• 모든 경우의 수에 대해 위와 같은 계산 과정을 반복하고, BFS 탐색 과정에서 1번 물통의 양 a가 0인 경우의 3번 물통의 양 c를 ans 배열에 추가해준다.
• ans를 정렬하고, 출력해주면 끝

import sys
from collections import deque

A,B,C=map(int, sys.stdin.readline().strip().split(' '))

queue=deque()
queue.append((0,0,C))
visited=set()
ans=[]
while queue:
    a,b,c=queue.popleft()
    if (a,b,c) in visited:
        continue
    visited.add((a, b, c))
    if a==0:
        ans.append(c)
    # 1->2
    if a+b>B:
        # 1->2로 물을 부을 때 2의 용량을 초과하는 경우
        queue.append((a+b-B, B, c))
    else:
        queue.append((0,a+b,c))
    # 1->3
    if a+c>C:
        queue.append((a+c-C,b,C))
    else:
        queue.append((0,b,a+c))
    # 2->1
    if a+b>A:
        queue.append((A,a+b-A,c))
    else:
        queue.append((a+b, 0,c))
    # 2->3
    if b+c>C:
        queue.append((a, b+c-C,C))
    else:
        queue.append((a, 0, b+c))
    # 3->1
    if a+c>A:
        queue.append((A, b, a+c-A))
    else:
        queue.append((a+c, b, 0))
    # 3->2
    if b+c>B:
        queue.append((a,B,b+c-B))
    else:
        queue.append((a,b+c,0))

ans.sort()
print(*ans, sep=' ')