[백준]2251번 물통 - C++

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

2251번: 물통

문제

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

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

입력

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

출력

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

---

물통은 총 3개인데 물의 총량은 항상 일정하다. 따라서 물통 2개의 물양만 알면 다른 하나의 물의 양도 알 수 있다.

BFS를 활용하여 from 물통에서 to 물통으로 물을 옮겨본다. from 물통이 비어있거나 to 물통이 가득 찼거나 이미 확인한 이동이라면 넘어간다. 그렇지 않다면 큐에 추가하여 향후 확인을 한다.

 

---

처음 제출했을때 시간초과가 났다. 처음 코드는 from물통이 비어있거나 to물통이 가득 찬 경우를 생각하지 않았다. 이 버전의 코드로 제출을 하였는데 틀렸습니다가 났다. 그래서 다시 한번 살펴보니 vis 배열을 [200][200]으로 선언을 했다. 범위를 210으로 바꾸니 정답이 되었다. 그래서 혹시나 하는 마음에 시간초과가 난 코드의 배열 범위를 바꿔보았더니 시간초과가 났다. 배열의 범위로 인해 틀렸습니다나 IndexOutOfRange는 봤어도 시간초과가 난 것은 처음 보는 것 같다. 애초에 배열을 왜 저렇게 잡지 않았으면 됐을 텐데 참 아쉽다!