[ 2251 ] [ BFS ] 물통

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

2251번: 물통

---

풀이 과정

---

1. 생각보다는 간단한데 조건이 너무 많아서 까다로움..
2. 초기에는 C 물통에만 물이 담겨져 있음.
3. BFS를 진행하면서 각각의 물통에 담겨져있는 물을 다른 물통으로 이동시킬 수 있는 모든 경우의 수 탐색
   
   1. 시작은 [0, 0, C 물통의 크기] => C 물통에만 물이 담겨져 있으므로.
   2. 각각의 물통에 담겨져있는 크기가 0보다 큰 경우 이동 가능
      1. a -> b,c / b -> a,c / c -> a, b 총 6가지 경우의 수 탐색
      2. 물이 넘치는 경우에는 옮기는 물통의 크기까지만 물을 넣고, 남은 물은 다시 자기 자신에 넣어줌.
   3. BFS를 진행하면서 a 물통의 크기가 0일 때의 c 물통의 크기들을 따로 저장
4. 저장해 둔 c 물통의 크기 리스트를 오름차순으로 정렬한 다음 출력
5. if문 조건 작성이 조금 난해하기도 하고, a 물통의 크기가 0일 때의 c 물통의 크기를 저장해야 하는것을 못봐서 그냥 c 물통의 크기를 저장했다가 계속 틀렸음.. 문제 잘 봐야 함.

---

소스 코드

---

import sys
from collections import deque

def bfs(max_a, max_b, max_c):
    answer = set()
    queue = deque()
    visited = set()
    queue.append([0, 0, max_c])
    visited.add(tuple([0, 0, max_c]))

    while queue:
        aL, bL, cL = queue.popleft()
        if aL == 0:
            answer.add(cL)

        # a -> b, c
        if aL > 0:
            if bL + aL <= max_b and (0, bL+aL, cL) not in visited:
                visited.add((0, bL+aL, cL))
                queue.append([0, bL+aL, cL])
            elif bL + aL > max_b and ((bL+aL)-max_b, max_b, cL) not in visited:
                visited.add(((bL+aL)-max_b, max_b, cL))
                queue.append([(bL+aL)-max_b, max_b, cL])

            if cL + aL <= max_c and (0, bL, cL+aL) not in visited:
                visited.add((0, bL, cL+aL))
                queue.append([0, bL, cL+aL])
            elif cL + aL > max_c and ((cL+aL)-max_c, bL, max_c) not in visited:
                visited.add(((cL+aL)-max_c, bL, max_c))
                queue.append([(cL+aL)-max_c, bL, max_c])

        # b -> a, c
        if bL > 0:
            if bL + aL <= max_a and (bL+aL, 0, cL) not in visited:
                visited.add((bL+aL, 0, cL))
                queue.append([bL+aL, 0, cL])
            elif bL + aL > max_a and (max_a, (bL+aL)-max_a, cL) not in visited:
                visited.add((max_a, (bL+aL)-max_a, cL))
                queue.append([max_a, (bL+aL)-max_a, cL])

            if cL + bL <= max_c and (aL, 0, cL+bL) not in visited:
                visited.add((aL, 0, cL+bL))
                queue.append([aL, 0, cL+bL])
            elif cL + bL > max_c and (aL, (cL+bL)-max_c, max_c) not in visited:
                visited.add((aL, (cL+bL)-max_c, max_c))
                queue.append([aL, (cL+bL)-max_c, max_c])

        # c -> a, b
        if cL > 0:
            if cL + aL <= max_a and (cL+aL, bL, 0) not in visited:
                visited.add((cL+aL, bL, 0))
                queue.append([cL+aL, bL, 0])
            elif cL + aL > max_a and (max_a, bL, (cL+aL)-max_a) not in visited:
                visited.add((max_a, bL, (cL+aL)-max_a))
                queue.append([max_a, bL, (cL+aL)-max_a])

            if cL + bL <= max_b and (aL, bL+cL, 0) not in visited:
                visited.add((aL, bL+cL, 0))
                queue.append([aL, bL+cL, 0])
            elif cL + bL > max_b and (aL, max_b, (bL+cL)-max_b) not in visited:
                visited.add((aL, max_b, (bL+cL)-max_b))
                queue.append([aL, max_b, (bL+cL)-max_b])
                
    return answer
            
        
    

a, b, c = map(int, sys.stdin.readline().rstrip().split())
temp = sorted(list(bfs(a, b, c)))
print(*temp)