백준 2251 물통 (파이썬)

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

2251번: 물통

1. 순열을 이용해서 물이 이동 가능한 경로를 저장해둔다

2. 물을 옮길 물통 번호(from)와 넣을 물통(to) 번호을 불러온다

3. 현재 0번 물통이 비었으면 2번 물통의 값을 ans에 기록한다

4. to가 넘치면 안되므로 한계치를 넘는지 검사한다

5. 조건에 맞게 from과 to의 물 양을 설정한다

6. bfs로 과정을 반복한 후 ans배열에 값이 있으면 해당 인덱스를 출력한다

from collections import deque
from itertools import permutations
import sys, copy

input = sys.stdin.readline

def bfs(x, y, z):
    q.append([x, y, z])
    check.append([x, y, z])
    while q:
        k = q.popleft()
        if k[0] == 0:
            ans[k[2]] = 1
        for i in range(len(t)):
            nfrom = t[i][0]
            nto = t[i][1]
            nk = copy.deepcopy(k)
            if k[nfrom] + k[nto] > limit[nto]:
                nk[nfrom] = k[nfrom] + k[nto] - limit[nto]
                nk[nto] = limit[nto]
            else:
                nk[nfrom] = 0
                nk[nto] = k[nfrom] + k[nto]
            if nk not in check:
                check.append(nk)
                q.append(nk)

a, b, c = map(int, input().split())
q, check, limit = deque(), [], [a, b, c]
ans = [0 for _ in range(c+1)]
t = list(permutations([0, 1, 2], 2))

bfs(0, 0, c)

for i in range(c+1):
    if ans[i] == 1:
        print(i, end=' ')