🧩 문제 : 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를 사용하는 것이 좋다.
🎁 성공!
'알고리즘' 카테고리의 다른 글
[BOJ / Python] 내일 할거야 (0) | 2023.01.16 |
---|---|
정렬 알고리즘 #선택 정렬/삽입정렬/퀵 정렬/계수 정렬 (0) | 2023.01.14 |
[BOJ / Python] 3020 개똥벌레 (0) | 2023.01.11 |
[BOJ / Python] 1541 잃어버린 괄호 (0) | 2023.01.09 |
[BOJ / Python] 1931 회의실 배정 (0) | 2023.01.09 |