2251: 물통

문제 링크

2251: 물통

구현 방식

• bfs를 이용한 brute force로 풀어주었다
• a -> b, a -> c, b -> a, b -> c, c -> a, c -> b의 모든 경우를 고려해주었다
• queue에는 현재 노드의 a, b, c의 물의 양을 넣어주었고, visit를 3차원 리스트로 선언하여 중복 제거 해주었다
  • 각 차원의 크기는 A의 물통 크기, B의 물통 크기, C의 물통 크기로 설정해줌

코드

import sys
from collections import deque
input = sys.stdin.readline

A, B, C = map(int, input()[:-1].split())
answer = []

queue = deque([]); queue.append((0, 0, C))
visit = [[[False]*(C+1) for _ in range(B+1)] for _ in range(A+1)]; visit[0][0][C] = True

while queue:
    a, b, c = queue.popleft()
    if a == 0: answer.append(c)

    #a -> b
    water = min(a, B-b)
    if not visit[a-water][b+water][c]:
        visit[a-water][b+water][c] = True
        queue.append((a-water, b+water, c))

    #a -> c
    water = min(a, C-c)
    if not visit[a-water][b][c+water]:
        visit[a-water][b][c+water] = True
        queue.append((a-water, b, c+water))

    #b -> a
    water = min(b, A-a)
    if not visit[a+water][b-water][c]:
        visit[a+water][b-water][c] = True
        queue.append((a+water, b-water, c))

    #b -> c
    water = min(b, C-c)
    if not visit[a][b-water][c+water]:
        visit[a][b-water][c+water] = True
        queue.append((a, b-water, c+water))

    #c -> a
    water = min(c, A-a)
    if not visit[a+water][b][c-water]:
        visit[a+water][b][c-water] = True
        queue.append((a+water, b, c-water))

    #c -> b
    water = min(c, B-b)
    if not visit[a][b+water][c-water]:
        visit[a][b+water][c-water] = True
        queue.append((a, b+water, c-water))

answer.sort()
print(" ".join(map(str, answer)))