[알고리즘] 25일차 (물의 양 구하기) #백준2251번

📌 문제 049) 물의 양 구하기

시간 제한 1초, 골드 V, 백준 2251번

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.
이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

입력

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

8 9 10 # A B C

출력

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

1 2 8 9 10

1단계 문제 분석

• 지금까지 접해 봤던 그래프 데이터를 저장하고 저장한 자료구조를 이용하는 방식과 달리, 그래프 원리를 적용해 그래프를 역으로 그리는 방식으로 접근하는 문제이다.
• A, B, C의 특정 무게 상태를 1개의 노드로 가정하고, 조건에 따라 이 상태에서 변경할 수 잇는 이후 무게 상태가 에지로 이어진 인접한 노드라고 생각하고, 문제에 접근해 보자.

1. 처음에 A, B는 비어 있고, C는 꽉 차 있으므로 최초 출발 노드를 (0, 0, 3번째 물통의 용량)으로 초기화한다.
2. BFS를 수행한다. 탐색 과정은 다음과 같다.
   1) 노드에서 갈 수 있는 6개의 경우(A -> B, A -> C, B -> A, B -> C, C -> A, C -> B)에 관해 다음 노드로 정해 큐에 추가한다. A, B, C 무게가 동일한 노드에 방문한 이력이 있을 때는 큐에 추가하지 않는다.
   2) 보내는 물통의 모든 용량을 받는 물통에 저장하고, 보내는 물통에는 0을 저장한다. 단, 받는 물통이 넘칠 때는 초과하는 값만큼 보내는 물통에 남긴다.
   3) 큐에 추가하는 시점에 1번째 물통(A)의 무게가 0일 때가 있으면 3번째 물통(C)의 값을 정답 리스트에 추가한다.
3. 정답 리스트를 오름차순 출력한다.

2단계 슈도 코드

Sender, Receiver(6가지 경우를 탐색하기 위한 리스트)
now(A, B, C의 값 저장)
visited(방문 여부 저장 리스트)
answer(정답 리스트)

# BFS 구현하기
BFS:
	큐 자료구조에 출발 노드 더하기 -> A와 B가 0인 상태이므로 0, 0 노드에서 시작하기
    visited 리스트에 현재 노드 방문 기록
    answer 리스트에 현재 C의 값 체크
	while 큐가 빌 때까지:
		큐에서 노드 데이터를 가져오기
        데이터를 이용해 A, B, C의 값 초기화
        for 6가지 케이스 반복: # A -> B, A -> C, B -> A, B -> C, C -> A, C -> B
        	받는 물통에 보내려는 물통의 값을 더하기
            보내려는 물통의 값을 0으로 업데이트하기
            if 받는 물통이 넘칠 때:
            	넘치는 만큼 보내는 물통에 다시 넣어 주고받는 물통은 이 물통의 최댓값으로 저장
            if 현재 노드의 연결 노드 중 방문하지 않은 노드:
            	큐에 데이터 삽입
                visited 리스트에 방문 기록
                if 1번째 물통이 비어 있을 때:
                	3번째 물통의 물의 양을 answer 리스트에 기록

BFS 수행

for answer 리스트 탐색:
	answer 리스트에서 값이 true인 index를 정답으로 출력

3단계 코드 구현

from collections import deque
# 두 리스트를 이용하여 6가지 이동 케이스를 간편하게 정의할 수 있다.
# 여기에서 0, 1, 2는 각각 A, B, C 물통을 뜻한다.
# 예시: index = 0의 경우 Sender[0]: 0, Receiver[0]: 1이기 때문에 A -> B 케이스를 뜻한다.

Sender = [0, 0, 1, 1, 2, 2]
Receiver = [1, 2, 0, 2, 0, 1]
now = list(map(int, input().split()))
visited = [[False for j in range(201)] for i in range(201)] # 물통 부피 용량 최대 200리터
answer = [False] * 201

def BFS():
    queue = deque()
    queue.append((0, 0))
    visited[0][0] = True
    answer[now[2]] = True
    while queue:
        now_Node = queue.popleft()
        A = now_Node[0]
        B = now_Node[1]
        C = now[2] - A - B # C는 전체 물의 양에서 A와 B를 뺀 것
        for k in range(6): # A -> B, A -> C, B -> A, B -> C, C -> A, C -> B
            next = [A, B, C]
            next[Receiver[k]] += next[Sender[k]]
            next[Sender[k]] = 0
            if next[Receiver[k]] > now[Receiver[k]]: # 물이 넘칠 때
                # 초과하는 만큼 다시 이전 물통에 넣 주기
                next[Sender[k]] = next[Receiver[k]] - now[Receiver[k]]
                next[Receiver[k]] = now[Receiver[k]] # 대상 물통 최대로 채우기
            if not visited[next[0]][next[1]]:
                visited[next[0]][next[1]] = True
                queue.append((next[0], next[1]))
                if next[0] == 0: # A의 물의 양이 0일 때 C의 물의 무게를 정답 변수에 저장
                    answer[next[2]] = True

BFS()

for i in range(len(answer)):
    if answer[i]:
        print(i, end=' ')