[백준] 2251 물통

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

각 바구니로 물을 이동시킬 때, 물을 최대한 많이 옮겨야했습니다.

A->B, A->C, B->A, B->C, C->A, C->B 로 물을 옮기도록 하는데, 두 바구니를 비교하여 이동가능한 물의 양을 구하여 이동시켰습니다.

탐색 여부를 확인하는 딕셔너리 변수를 이용하여 중복 탐색을 방지하였습니다.

딕셔너리 변수의 키 값으로는 (A바구니 물의 양, B바구니 물의 양)으로 지정하였습니다.

2) 알고리즘

• BFS

3) 풀이 코드

사용 언어 - Python

import sys
from collections import deque
sys.stdin = open('input.txt')

def solution():
    q = deque([(0, 0)])                 # 처음 A, B 물통은 비어있음

    while q:
        a, b = q.popleft()              # 현재 A, B 바구니 물의 양
        c = C - a - b                   # C 바구니 물의 양

        if not a:                       # A 바구니가 비어있다면, 정답에 추가
            answer.add(c)
        
        for element in [(a + min(c, A-a), b), (a, b + min(c, B-b)),         # C -> A, C -> B 바구니로 물을 옮김
            (a + min(b, A-a), b - min(b, A-a)), (a, b - min(b, C-c)),       # B -> A, B -> C 바구니로 물을 옮김
            (a - min(a, B-b), b + min(a, B-b)), (a - min(a, C-c), b)]:      # A -> B, A -> C 바구니로 물을 옮김
            
            if not visited.get((element[0], element[1]), False):            # A 바구니와 B 바구니에 남은 물의 양을 탐색하지 않았으면
                visited[(element[0], element[1])] = True                    # 탐색 처리
                q.append((element[0], element[1]))                          # 큐에 추가
        
A, B, C = map(int, sys.stdin.readline().split())        # 물통의 최대양
answer = set()                                          # 정답의 집합
visited = {}                                            # A, B 물통에 현재 담겨있는 물의 양을 탐색했는지 여부

solution()

print(*sorted(answer))              # 오름차순 출력

---

🔗 문제 링크

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

2251번: 물통

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다