[백준] 2251 물통 (골드 5)

물통의 상태를 매번 큐에 넣어주면서

 

이전에 도달하지 못했던 상태면 큐에 삽입해주고 방문처리를 하는 방식으로 진행했다.

 

미로찾기와 같은 형태의 상황만 bfs를 사용하는 것이 아니라,

현재의 상태에서 다음 상태로 연결되는 상황이기만 한다면 bfs를 떠올려보아야 한다.

 

visited 는 (A, B, C)에 들어있는 물의 양의 튜플이 들어가는 set으로 정의했는데, 

문제를 다 풀고 생각해보니, 물의 총량은 일정하기 때문에 3개의 물통 중 2개의 물통에 들어있는 양만 저장하면 된다.

 

즉, visited를 200*200의 2차원 배열로 만들었어도 충분히 가능했다는 말이다.

시간복잡도 측면에서 약간 이득이 될 것 같다.

 

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

A, B, C = map(int, input().rstrip().split())

queue = deque()
visited = set()

queue.append((0,0,C))
visited.add((0,0,C))

answer = []

while queue:

    a, b, c = queue.popleft()

    if a == 0:
        answer.append(c)


    ## 1->2로 붓기
    now = min(a+b, B)
    if (a+b-now,now,c) not in visited:
        queue.append((a+b-now,now,c))
        visited.add((a+b-now,now,c))

    ## 1->3로 붓기
    now = min(a+c, C)
    if (a+c-now,b,now) not in visited:
        queue.append((a+c-now,b,now))
        visited.add((a+c-now,b,now))


    ## 2->1로 붓기
    now = min(a+b, A)
    if (now,a+b-now,c) not in visited:
        queue.append((now,a+b-now,c))
        visited.add((now,a+b-now,c))

    ## 2->3로 붓기
    now = min(b+c, C)
    if (a,b+c-now,now) not in visited:
        queue.append((a,b+c-now,now))
        visited.add((a,b+c-now,now))


    ## 3->1로 붓기
    now = min(a+c, A)
    if (now,b,a+c-now) not in visited:
        queue.append((now,b,a+c-now))
        visited.add((now,b,a+c-now))

    ## 3->2로 붓기
    now = min(b+c, B)
    if (a,now,b+c-now) not in visited:
        queue.append((a,now,b+c-now))
        visited.add((a,now,b+c-now))


answer.sort()
for item in answer:
    print(item, end=" ")