[백준] 2251 파이썬(python) : 물통 - (★)

2251번 : 물통

 

 

문제를 읽는 순간 1697번 : 숨바꼭질 같은 문제라고 생각했다. bfs를 이용한 정형화되어있지 않은 유형이라 생각했는데 부피가 A인 물통이 비어있을 때 C물통의 용량을 구하는 방법은 q.popleft()로 꺼내줄때 조건문을 사용하면 되지만,다른 물통으로 물을 옮기는것을 구현하는 방법과 방문처리를 구현하는 방법이 떠오르지 않았다.

완전탐색으로 A에서 B, C로 옮길때 B에서 A, C로 옮길때 C에서 A, B로 옮길때 6가지 경우를 모두 따져야하며 물을 따를때마다 A물통의 양이 0인 경우를 찾아야 한다. 문제의 조건에서 C물통은 처음 시작할때 가득 채워져 있고 나머지 두 물통은 비워져 있닥고 했으므로 물의 총량은 고정이다. 그래서 C물통의 남아있는 양인 z를 구하는 공식은 z = C-x-y로 찾을 수 있다. 방문처리는 A, B 물통의 남은 양을 이용해서 중복방지를 할 수 있다. A와 B가 같은 양을 품고 있는 경우는 유일하기 때문에 2차원 리스트로 표현이 가능하다.

 

import sys
from collections import deque
a, b, c = map(int, sys.stdin.readline().split())
visit = [ [False]*(b+1) for _ in range(a+1) ] #1
visit[0][0] = True #2
res = []
q = deque()
q.append((0, 0))

def pour(x, y): #3
    if not visit[x][y]:
        visit[x][y] = True
        q.append((x, y))

def bfs():
    while q:
        x, y = q.popleft()
        z = c - x - y #4
        if x == 0: #5
            res.append(z)
        
        water = min(x, b-y) #6
        pour(x-water, y+water) #7
        
        water = min(x, c-z)
        pour(x-water, y)
        
        water = min(y, a-x)
        pour(x+water, y-water)
        
        water = min(y, c-z)
        pour(x, y-water)
        
        water = min(z, a-x)
        pour(x+water, y)
        
        water = min(z, b-y)
        pour(x, y+water)
        
    res.sort()
    print(*res) #8
bfs()

 

#1 : 내부로 들어가는 리스트가 b인것은 물통의 순서를 세어줄때 a를 먼저 세어주기 때문에 a로 들어가서 b물통을 찾기 때문이다. b+1인 이유는 물의 양이 0인 경우와 가득채워져 있는 경우가 있기 때문이다.

#2 : 첫위치 방문처리

#3 : 물을 따르는 함수

#4 : 두 변수를 알기 떄문에 C물통의 남아 있는 물의 양인 z를 구할 수 있다.

#5 : x가 0일때의 z를 리스트에 추가

#6 : A에서 B로 물을 부을때 문제의 조건에 따라 부울 수 있으므로 B에서 y를 뺀값과 A중 더 작은 값을 옮길 수 있다.

#7 : 옮길 수 있는 양을 water라 할때 두 변수로 방문처리를 할 수 있으므로 x와 y 값을 조정하여 함수에 인자로 넣어준다.

#8 : while q: 가 끝나면 최종정렬 후 출력