[백준]2251번: 물통

물통

물통

문제

---

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

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

입력

---

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

출력

---

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

예제 입력 1

8 9 10

예제 출력 1

1 2 8 9 10

문제 해석

• 물통에 물을 계속 옮기는 하노이 탑과 비슷한 문제이다.
• 무조건 한쪽이 빌때까지 옮기거나 한쪽이 가득 찰때까지 옮기는 것이 규칙이다.
• A가 비어있는 경우만 정답으로 처리한다.

풀이

• A B C 입력 받음
• 중복되는 값을 없애기 위해 comb_set이라는 set() 자료형 선언
• bfs 함수 선언
  • queue.popleft()
  • c != 0:
    • c -> a
    • c -> b
  • b != 0:
    • b -> a
    • b -> c
  • a != 0:
    • a -> b
    • a -> c

추가적으로 생각해야할 조건

• 예를 들어 c에서 b로 옮기는 경우
  • c를 전부 b에 부었을 때 b 전체 용량을 넘어가는 경우
    • c_b = (c + b) - b의 전체 용량
    • comb_set에 (a, b의 전체 용량, c_b)가 존재하지 않는다면
      • comb_set.add
      • queue.append
  • 같거나 넘어가지 않는 경우
    • comb_set에 (a, b + c, 0)가 존재하지 않는다면
      • comb_set.add
      • queue.append
• 정답인 경우의 수는 a가 0일때 c의 값이다.
• for i in comb_set:
  • if i[0] == 0:
    • list에 append
• list를 정렬 후 출력

점화식

import sys
from collections import deque

A, B, C = map(int, sys.stdin.readline().split())

def bfs():
    queue = deque()
    queue.append([0, 0, C])
    comb_set = set()
    comb_set.add((0, 0, C))
    while queue:
        a, b, c = queue.popleft()
        if c != 0:
            if a != A:
                c_a = c + a
                if c_a >= A:
                    c_a = c_a - A
                    if (A, b, c_a) not in comb_set:
                        comb_set.add((A, b, c_a))
                        queue.append([A, b, c_a])
                else:
                    if (c_a, b, 0) not in comb_set:
                        comb_set.add((c_a, b, 0))
                        queue.append([c_a, b, 0])
            if b != B:
                c_b = c + b
                if c_b >= B:
                    c_b = c_b - B
                    if (a, B, c_b) not in comb_set:
                        comb_set.add((a, B, c_b))
                        queue.append([a, B, c_b])
                else:
                    if (a, c_b, 0) not in comb_set:
                        comb_set.add((a, c_b, 0))
                        queue.append([a, c_b, 0])
        if b != 0:
            if a != A:
                b_a = b + a
                if b_a >= A:
                    b_a = b_a - A
                    if (A, b_a, c) not in comb_set:
                        comb_set.add((A, b_a, c))
                        queue.append([A, b_a, c])
                else:
                    if (b_a, 0, c) not in comb_set:
                        comb_set.add((b_a, 0, c))
                        queue.append([b_a, 0, c])
            if c != C:
                b_c = c + b
                if b_c >= C:
                    b_c = b_c - C
                    if (a, b_c, C) not in comb_set:
                        comb_set.add((a, b_c, C))
                        queue.append([a, b_c, C])
                else:
                    if (a, 0, b_c) not in comb_set:
                        comb_set.add((a, 0, b_c))
                        queue.append([a, 0, b_c])
        if a != 0:
            if c != C:
                a_c = c + a
                if a_c >= C:
                    a_c = a_c - C
                    if (a_c, b, C) not in comb_set:
                        comb_set.add((a_c, b, C))
                        queue.append([a_c, b, C])
                else:
                    if (0, b, a_c) not in comb_set:
                        comb_set.add((0, b, a_c))
                        queue.append([0, b, a_c])
            if b != B:
                a_b = a + b
                if a_b >= B:
                    a_b = a_b - B
                    if (a_b, B, c) not in comb_set:
                        comb_set.add((a_b, B, c))
                        queue.append([a_b, B, c])
                else:
                    if (0, a_b, c) not in comb_set:
                        comb_set.add((0, a_b, c))
                        queue.append([0, a_b, c])
    ans = []
    visited = [False] * (C + 1)
    for i in comb_set:
        if visited[i[2]] == False:
            if i[0] == 0:
                visited[i[2]] = True
                ans.append(i[2])
    ans.sort()
    print(*ans)
bfs()

고찰

• 총 6개의 경우의 수가 있었는데 예외 처리만 잘 해주면 어렵지 않은 bfs문제였다.