[백준] 2251(파이썬) - 물통

resilient

·

2021. 8. 14. 16:10

728x90
반응형

https://www.acmicpc.net/problem/2251

 

2251번: 물통

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부

www.acmicpc.net

  • 이 문제를 읽고 나서 처음 든 생각은 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=" ")
반응형