[Gold V] 물통 - 2251 (그래프 탐색/BFS)

[Gold V] 물통 - 2251

문제 링크

성능 요약

메모리: 115512 KB, 시간: 132 ms

분류

너비 우선 탐색(bfs), 깊이 우선 탐색(dfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 A, B, C가 주어진다.

출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

1.물을 옮길 수 있는 경우의 수를 구한다.(a->b, a->c, b->a, b->c, c->a, c->b)

2. 물을 옮길 수 있는 경우의 수마다 bfs를 돌리고 옮긴 후의 x와 y의 상태를 큐에 저장하여 중복 제거를 위해 방문체크

2.a물통이 비어있을 때 answer에 c물통에 들어있는 물의 양 추가

3.