[백준/BOJ] - 2251번 python 풀이 - bfs

---

위 문제는 DFS,BFS 모두 가능한데 BFS로 풀었다.

 

1. 물통 크기를 각각 a, b, c로 설정한다.

2. 각 물통에 있는 물의 크기를 x, y, z로 설정한다.

3. x, y, z 각각의 경우의 수를 방문처리 하려고 직관적으로 접근하면 3차원 배열을 만들어야 하므로 

4. x, y 물의 양으로 z를 도출할 수 있는 점을 이용하여 x, y만을 가지고 로직을 구성하였다.

z = c(돌고도는 총 물의 양) - x(현재 a의 물의 양) - y(현재 b의 물의 양)

 

문제 조건에 의해 a 물통이 비었을 경우 c 물통에 있는 물의 크기를 구해야 하므로

queue를 돌며 a가 비었을 경우의 c물통에 있는 물의 크기를 answer에 추가한다.

 

경우의 수는 총 6가지

x → y

x → z

y → x

y → z

z → x

z → y

 

예시로 x → y의 경우

x에 남아있는 물의양 vs y에 넣을 수 있는 물의양 중 작은 값을 기준으로

water = min(x,b-y)

 

x, y의 값이 변경하게 된다.

pour(x-water, y+water)

 

앞서 언급했듯이 z값은 알아서 계산되므로 x, y 만 잘 정해서 queue에 삽입하면 되는 구조이다.

---

from collections import deque
import sys
input = sys.stdin.readline
a,b,c = map(int,input().split())
ok = [[False] * (b+1) for _ in range(a+1)]
answer = []
queue = deque()

def pour(x,y):
    if not ok[x][y]:
        ok[x][y] = True
        queue.append((x,y))

def bfs():
    queue.append((0,0))
    ok[0][0] = True
    while queue:        
        x,y = queue.popleft()
        z = c - x - y #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()
print(*sorted(answer))

---

참조: https://eboong.tistory.com/428

[2251] 물통 in python