[백준2251] 물통

문제

---

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

2251번: 물통

 

생각의 흐름

---

1. 편의상 물통을 각각 x,y,z라고 하자. 물이 담겨 있는 것을 "특정한 상태"라고 바라보자. 그러면 이 특정상태는 x,y에 담긴 물의 양의로 정의 가능하다. 왜냐하면 z물통의 양은 C-x-y이니까.(이것이 이 문제를 BFS로 풀 수 있도록 해주는 열쇠이다.)
2. 물을 옮길 수 있는 경우의 수는 총 6가지이다.(x->y, x-z, y->x, y->z, z->x, z->y)
3. x 물통 속 물의 양이 0이 되면 그 때 z 물통 속의 물의 양을 저장한다.
4. 이 때 예를들어, x->y로 물을 옮긴다고 할 때 옮겨지는 물의 양은 min(x, b-y)이다.

 

깨달은 점

---

왜 본 문제를 BFS를 사용해서 풀어야 할까?

• 물을 옮길 수 있는 경우의 수는 무척 많다. 단순히 x->y로 옮겼다고 끝난 것이 아니라 그것을 이리저리 옮겨가며 특정 수를 만들어 더해줄 수 있기 때문이다. 그렇기에 강력한 탐색 알고리즘을 사용해서 모든 경우를 검사해봐야 한다. BFS는 강력한 탐색 방법 중 하나이다.
• 단순한 순열 문제인 것 같지만 어떤 시점에 물이 차있는 것을 특정한 상태로 바라보면 BFS로 푸는 것이 가능하다. 가령, 앞의 두 물통에 물의 양이 3, 4 만큼 차있다고 가정하자. 그럼 이 특정한 '상태'에서는 앞으로 진전될 수 있는 상태가 딱 정해지게 된다. 때문에 visit[3][4]를 True로 처리해두고 다시 검사(방문)하지 않아도 되는 것이다.

 

코드

---

# BOJ 2251
from collections import deque

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

def bfs():
    q.append((0,0)) #처음 시작 상태
    visit[0][0]=True
    while q:
        x,y=q.popleft()
        z=c-x-y
        if x==0:
            ans.append(z)
        # 물 옮기는 6가지 경우(x->y,x->z,y->x,y->z,z->x,z->y)
        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=list(map(int, input().split()))
q = deque()
ans = []
visit = [[False]*(b+1) for _ in range(a+1)]
bfs()
ans.sort()
print(' '.join(map(str, ans)))