백준 2251: 물통 - 그래프 탐색 (파이썬)

물통 성공다국어

2251번: 물통

문제

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

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

입력

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

출력

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

출처

Olympiad > USA Computing Olympiad > 2000-2001 Season > USACO Winter 2001 Contest > Orange 4번

 

내 코드

import sys

def func(a,b,c):
    if a==0: #a가 0일 때 c 상태 저장.
        answer.append(c)
    
    #C->A case1
    if c>0 and a<A:
        tmp1=a
        tmp3=c
        while tmp3>0 and tmp1<A:
            tmp3-=1
            tmp1+=1
        if [tmp1,b,tmp3] not in save:
            save.append([tmp1,b,tmp3])
            func(tmp1,b,tmp3)
    
    #C->B case2
    if c>0 and b<B:
        tmp2=b
        tmp3=c
        while tmp3>0 and tmp2<B:
            tmp3-=1
            tmp2+=1
        if [a,tmp2,tmp3] not in save:
            save.append([a,tmp2,tmp3])
            func(a,tmp2,tmp3)

    #B->A case3
    if b>0 and a<A:
        tmp1=a
        tmp2=b
        while tmp2>0 and tmp1<A:
            tmp2-=1
            tmp1+=1
        if [tmp1,tmp2,c] not in save:
            save.append([tmp1,tmp2,c])
            func(tmp1,tmp2,c)


    #B->C case4
    if b>0 and c<C:
        tmp2=b
        tmp3=c
        while tmp2>0 and tmp3<C:
            tmp2-=1
            tmp3+=1
        if [a,tmp2,tmp3] not in save:
            save.append([a,tmp2,tmp3])
            func(a,tmp2,tmp3)

    

    #A->B case5
    if a>0 and b<B:
        tmp1=a
        tmp2=b
        while tmp1>0 and tmp2<B:
            tmp1-=1
            tmp2+=1
        if [tmp1,tmp2,c] not in save:
            save.append([tmp1,tmp2,c])
            func(tmp1,tmp2,c)
    

    #A->C case6
    if a>0 and c<C:
        tmp1=a
        tmp3=c
        while tmp1>0 and tmp3<C:
            tmp1-=1
            tmp3+=1
        if [tmp1,b,tmp3] not in save:
            save.append([tmp1,b,tmp3])
            func(tmp1,b,tmp3)


#각 물통의 고유 용량 A, B, C
A,B,C=map(int,sys.stdin.readline().split())


answer=[]
save=[]
save.append([0,0,C])

func(0,0,C)

answer.sort()

print(*answer)

 

풀이 및 접근)

- A가 비어있을 때 C의 상태를 일반화 시키는 것은 불가능하고 모든 경우의 수를 다 해야 알 수 있다고 판단하였다. 따라서 모든 경우의 수를 체크하도록 했다.

- 물을 붓다보면 분명 중복되는 상태가 나와서 중단 조건이 필요했다. 물통 A, B, C에 물이 담겨있는 상태가 이미 나왔던 적이 있으면 그 겨우에 대해서는 더이상 물 붓기를 진행하지 않는다.

- 물을 붓는 경우는 총 6가지 이다. A->B, A->C / B->A, B->C / C->A, C->B 이다. 코드에서는 문제 상황상 C부터 붓기가 시작되어 C에서 붓는 경우부터 작성하였다.(참고)

- 물을 부을 수 있는 상황은 예를들어, A->B일때 A를 시작점, B를 도착점이라 할 때

    *시작점에 물이 있어야 하고 도착점은 그것의 최대용량보다 적게 물이 담겨있어야 한다.

    *물 붓기가 종료되는 상황은

        *시작점의 물이 다 떨어지거나

        *도착점에 물이 다 차거나 이다.

- 위의 상황들을 코드를 통해 구현하였다.

- 물 붓기가 끝난 상황의 상태가 이미 일어난 상태라면, 이 상태를 저장하지 않고 이것에 대해 물 붓기를 진행하지 않는다.