[BOJ / Python] 2251 물통

🧩 문제 : 2251번

 

💪🏻 해결 방법 

1️⃣ BFS 이용

1. 물의 총량은 c 이기 때문에, 물병 z에 담긴 물의 양은 c - 물병 x에 담긴 물 - 물병 y에 담긴 물 

2. visited[x][y]로 경우의 수 중복 방지

3. 물의 양이 x = 0, y = 0 일 때 부터 경우의 수를 토대로 BFS를 한다.       

 (1) 물병 x에 담긴 물이 0이라면 물병 z에 담긴 물의 양을 result에 담는다. 

 (2) x -> y, x -> z, y -> x, y -> z, z -> x, z -> y 총 6가지를 모두 탐색한다.

 (3) 각각의 경우에 따라 옮길 수 있는 물의 양 파악 후, 물을 옮긴다.

water = min(x, b - y) : x에서 y로 옮길 물.  x 물통에서 y 물통으로 들어 갈 수 있는 물의 양을 체크한다. 
pour(x - water, y + water) :  체크한 물 양을 x 물통에서 빼주고 y 물통에 넣어 경우의 수 탐색

위 그림과 같이 y -> x로 물을 옮긴다고 해보자.

물병 y에서는 2L의 물을 보낼 수 있지만, 물병 x에는 1L(물병 x의 총량 - 물병 x에 담긴 물의 양 = 2 - 1)의 물만 받을 수 있으므로 물병 y에서 물병 x로 1L의 물이 옮겨진다. 

 

4. 탐색이 끝났다면 오름차순 정렬 후 출력 

 

 

정답 코드 

import sys
from collections import deque

# x 물통과 y 물통의 경우의 수 저장
def pour(x, y):
    if not visited[x][y]:
        visited[x][y] = True
        q.append((x, y))


# bfs 탐색
def bfs():

    while q:
        # x : a 물통의 물의 양, y : b 물통의 물의 양, z : c 물통의 물의 양
        x, y = q.popleft()
        z = c - x - y

        # x 물통이 비어있는 경우 z 물통에 남아있는 물의 양 저장
        if x == 0:
            res.append(z)

        # x -> y
        # x 물통에서 y 물통으로 들어 갈 수 있는 물의 양 체크
        # 체크한 물 양을 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)


a, b, c = map(int, sys.stdin.readline().split())


# 경우의 수를 담을 큐
q = deque()
q.append((0, 0)) # x 물통과 y 물통의 물의 양이 0일때부터 탐색

# 방문 여부
visited = [[False] * (b+1) for _ in range(a+1)]
visited[0][0] = True

# x 물통의 양이 0일 때 z 물통의 양
res = []

bfs()

# 오름차순 정렬 후 출력
res.sort()
print(*res)

 

☁️ 새로 알게 된 사실 

list의 pop()보다 deque의 popleft()가 처리속도가 더 빠르다 

• pop() : 0번째 요소를 꺼낸 다음 뒤에 있는 것들을 한칸식 앞으로 당겨오는 작업을 함 - O(n)
• popleft() : 0번째 요소를 꺼내면 끝 - O(1)

 

따라서 요소를 꺼낼 일이 많은 문제에서는 deque를 사용하는 것이 좋다. 

 

🎁 성공!