[BOJ] 2251 물통 Python

문제

각각 부피가 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

풀이

참고 : https://cijbest.tistory.com/14

[백준 2251 : PYTHON] 물통

import sys
from collections import deque
input = sys.stdin.readline

# 입력(리터 범위)
a, b, c = map(int, input().split())

# 경우의 수를 담을 큐
q = deque()
q.append((0, 0))

# 방문 여부 (visited[x][y])
visited = [[False]*(b+1) for _ in range(a+1)]
visited[0][0] = True

# 답을 저장할 배열
answer = []

# x, y의 경우의 수 저장
def pour(x, y):
    if not visited[x][y]:
        visited[x][y] = True
        q.append((x, y))

def bfs():
    while q:
        # x : a물통의 물의 양, y : b물통의 물의 양, z : c물통의 물의 양
        x, y = q.popleft()
        z = c-x-y

        # a 물통이 비어있는 경우 c 물통에 남아있는 양 저장
        if x == 0:
            answer.append(z)

        # x->y
        water = min(x, b-y)
        pour(x-water, y+water)
        # x->z
        water = min(x, c-z)
        pour(x-water, y)
        # y->x
        water = min(y, a-x)
        pour(x+water, y-water)
        # y->z
        water = min(y, c-z)
        pour(x, y-water)
        # z->x
        water = min(z, a-x)
        pour(x+water, y)
        # z->y
        water = min(z, b-y)
        pour(x, y+water)

bfs()

#출력
answer.sort()
for i in answer:
    print(i, end=' ')

후기

처음엔 세 번째 물통보다 작은 용량을 가진 것을 기준으로 두고 규칙을 찾아서 풀었다. -> 14퍼센트에서 틀림..

내 생각대로 규칙을 찾으려 하지 말고 자료구조를 생각하면서 문제를 풀어야 한다.

이 문제의 경우 물을 옮기는 방법의 수를 찾는 것이 핵심이었다.

그리고 두 물통의 양이 정해지면 나머지 하나는 자동으로 정해지니 x, y 두개만 가지고 방문처리를 해주면 된다!

 

water = min(x, b - y) : x에서 y로 옮길 물. x 전체를 옮기거나 b물통을 꽉 채우는 방법이 있다.

pour(x - water, y + water) : 옮긴 후의 x와 y의 상태를 큐에 저장한다.

 

코드 복습 하기

 

스스로 뚝딱 풀어내는 그날이 올 때까지..