[python] 백준 2251 물통

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

2251번: 물통

 

문제 해결

• 하노이탑 같은 문제 느낌이 들었다.
• x+y+z = c (c는 상수)이므로 x,y를 변수로 두면 z는 알아서 구해진다.
• bfs문제로 푸는 것이 좋을 듯 싶다.

 

CODE

from collections import deque

sender = [0, 0, 1, 1, 2, 2]
receiver = [1, 2, 0, 2, 0, 1]
limit = list(map(int, input().split()))
visited = [[False for _ in range(201)] for _ in range(201)]
ans = [False]*201

def bfs():
    que = deque()
    que.append((0,0))
    visited[0][0] = True
    ans[limit[2]] = True
    while que:
        now_node = que.popleft()
        a = now_node[0]
        b = now_node[1]
        c = limit[2] - a- b
        for i in range(6):
            next = [a,b,c]
            next[receiver[i]] += next[sender[i]]
            next[sender[i]] = 0
            if next[receiver[i]] > limit[receiver[i]]:
                next[sender[i]] = next[receiver[i]]-limit[receiver[i]]
                next[receiver[i]] = limit[receiver[i]]
            if not visited[next[0]][next[1]]:
                visited[next[0]][next[1]] = True
                que.append((next[0], next[1]))
                if next[0] ==0:
                    ans[next[2]]= True
bfs()
for i in range(len(ans)):
    if ans[i]:
        print(i, end=' ')