[백준] 2251(파이썬) - 물통
resilient
·2021. 8. 14. 16:10
728x90
반응형
https://www.acmicpc.net/problem/2251
- 이 문제를 읽고 나서 처음 든 생각은 BFS로 풀어야겠다 였다.
- 근데 q를 만들어서.. while로 돌리는데... 뭘 넣어주지? 하다가 경우의 수를 다 따져서 if else 문을 구현했다.
- 3개의 물컵 중에 2개의 물컵 양을 알면 나머지 물컵 양을 알 수 있기 때문에 방문처리를 2차원 배열로 구현했다.
- q리스트에 원소가 없을 때까지 while문이 돌고 a물컵양이 0일 때 c물컵 양 체크리스트를 만들어서 해당 인덱스의 값을 0에서 1로 변경해준다.
- 나중에 BFS가 끝나고, c물컵양 체크리스트를 만들어서 값이 1인 인덱스만 출력해주면 된다.
import sys
from collections import deque
input = sys.stdin.readline
A, B, C = map(int, input().split())
Max = max(A,B,C)
c_check = [0 for _ in range(Max+1)]
visited = [[0]*201 for _ in range(Max+1)]
q = deque()
q.append([0,0,C])
def bfs():
while q:
a,b,c = q.popleft()
if visited[a][c] == 1:
continue
else:
visited[a][c] = 1
if a == 0:
c_check[c] = 1
if a + b > B:
q.append([a + b - B, B, c])
else:
q.append([0, a + b, c])
if a + c > C:
q.append([a + c - C, b, C])
else:
q.append([0, b, a + c])
if b + a > A:
q.append([A, b + a - A, c])
else:
q.append([b + a, 0, c])
if b + c > C:
q.append([a, b + c - C, C])
else:
q.append([a, 0, b + c])
if c + a > A:
q.append([A, b, c + a - A])
else:
q.append([c + a, b, 0])
if c + b > B:
q.append([a, B, c + b - B])
else:
q.append([a, c + b, 0])
bfs()
for i in range(Max+1):
if c_check[i] == 1:
print(i,end=" ")
반응형
'자료구조 & 알고리즘 > 백준(Baekjoon)' 카테고리의 다른 글
[백준] 1916(파이썬) - 최소비용구하기 (0) | 2021.08.25 |
---|---|
[백준] 1753(파이썬) - 최단경로 (2) | 2021.08.21 |
[백준] 2407(파이썬) - 조합 (0) | 2021.08.12 |
[백준] 2023(파이썬) - 신기한 소수 (0) | 2021.08.11 |
[백준] 10830(파이썬) - 행렬 제곱 (0) | 2021.08.10 |