[백준/2251] 물통 (Python)

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

2251번: 물통

 

Difficulty : Gold 5

 

Status : Solved

 

Time : 00:12:30

 

---

 

문제 설명

 

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

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

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

8 9 10

 

출력 예시

 

1 2 8 9 10

 

 

---

 

풀이

 

a, b, c에 담긴 초기 물의 양을 (0, 0, C)라고 할 때, 모든 가능한 경우의 수를 탐색하는 게 포인트이다. DFS 및 BFS를 사용하되,

 

• 한 컵에서 다른 컵으로 물을 부을 때의 처리를 확실히 하고
• c의 물의 양에 따라 방문하는 경우의 수를 저장해야 하며
• 이 중 a가 비었을 때(0일 때) c의 값을 저장해서 탐색 종료 후 출력해야한다.

조건만 만족한다면 c = 0일때 역시 출력해야 한다(나는 물이 있어야만 하는줄 알았지...)

 

 

풀이 코드

from collections import defaultdict, deque

limit_list = list(map(int, input().split()))
C = limit_list[-1]
visited = defaultdict(set)
visited[C].add((0, 0))
q = deque([[0, 0, C]])
result = set([C])

while q :
  a, b, c = q.popleft()

  for i in range(3) :
    for j in range(3) :
      if i == j :
        continue
      next_list = [a, b, c]
      diff = min(limit_list[j] - next_list[j], next_list[i])
      next_list[i] -= diff
      next_list[j] += diff

      next_tuple = tuple(next_list[:2])
      if next_tuple not in visited[next_list[2]] :
        visited[next_list[2]].add(next_tuple)
        q.append(next_list)
        if not next_tuple[0] :
          result.add(next_list[2])

result = sorted(list(result))
print(*result)

풀이 완료!