728x90
위 문제는 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
728x90
'백준 풀이' 카테고리의 다른 글
[백준/BOJ] - 13265번 python 풀이 - bfs (0) | 2023.03.27 |
---|---|
[백준/BOJ] - 5014번 python 풀이 - bfs (0) | 2023.03.27 |
[백준/BOJ] - 24230번 python 풀이 - dfs (0) | 2023.03.15 |
[백준/BOJ] - 3187번 python 풀이 - dfs (0) | 2023.03.13 |
[백준/BOJ] - 1303번 python 풀이 - dfs (0) | 2023.03.13 |