[알고리즘][백준 14867] 물통

문제 링크

백준 14867 문제 링크

문제 정의

입력
물통 A의 용량, 물통 B의 용량, 물통 A에 남겨야 하는 물, 물통 B에 남겨야 하는 물
ex) 3 7 3 2
용량이 3, 7인 두개의 물통이 있고 이것을 이용해서 최종 물 용량을 3, 2로 만들어라.

"이동 알고리즘"
1. Fill x -> x 물통을 꽉 채운다.
2. Empty x -> x 물통을 비운다.
3. Move water from x to y -> x에 있는 물을 y로 붇는다.(자세한건 문제 링크 참고)

출력
최종 물 용량으로 만들때까지 걸리는 "이동 알고리즘" 횟수

문제 풀이

출력값은 횟수다. 그리고 이 횟수들을 하나하나 더해갈 때 들어가는 가중치는 존재 하지 않는다. 어떤 말이냐면 이동 알고리즘 중 Fill x와 Empty x를 할 때, 횟수의 카운트가 올라가는 거지, 어떤 값을 치루는 게 아니라는 것이다. 예를들어 Fill x는 3의 비용이 들고, Empty x는 5의 비용이 든다던지...

따라서 가중치가 없으므로 이것은 BFS로 풀 확률이 높다. 왜냐하면 BFS로 한층 한층 찾아가다가 원하는 답이 딱 나오면 그때의 층 수를 얘기해주면 그것이 답이기 때문이다.

지금부터 이 문제를 풀겠다. 우리가 원하는 것은 최종 물 용량을 만들때까지 필요한 횟수.
현재의 물 상태를 x, y라 하고, 물통의 이름을 a, b라 하고, 최종 목표 물 용량을 c, d라고 하자.

현재의 물 상태 x, y에서는 총 6개의 작업을 진행할 수 있다.

6개의 작업
	1. 물통 a 꽉 채우기
    	2. 물통 b 꽉 채우기
    	3. 물통 a 비우기
    	4. 물통 b 비우기
    	5. 물통 a에 있는 물을 b로 옮기기.
    	6. 물통 b에 있는 물을 a로 옮기기.

처음 위치에서 BFS로 위의 6개의 작업들을 실행한다.
실행할 때마다 실행이 끝나고 난 후의 x, y위치가 한번도 가보지 않은 곳이라면 큐에 넣는다.
x,y가 c,d랑 일치하면 그때의 층(BFS의 층)을 출력한다.

내 코드

import sys
from _collections import deque

a, b, c, d = map(int, sys.stdin.readline().split())


visit = {}

def bfs():
    queue = deque()
    queue.append((0, 0))
    visit[(0, 0)] = 1

    if c == 0 and d == 0:
        return 0
    
    while queue:

        x, y = queue.popleft()

        # a 가득채우기
        if not visit.get((a, y)):
            queue.append((a, y))
            visit[(a, y)] = visit[(x, y)] + 1

        # b 가득채우기
        if not visit.get((x, b)):
            queue.append((x, b))
            visit[(x, b)] = visit[(x, y)] + 1


        # a 비우기
        if not visit.get((0, y)):
            queue.append((0, y))
            visit[(0, y)] = visit[(x, y)] + 1


        # b 비우기
        if not visit.get((x, 0)):
            queue.append((x, 0))
            visit[(x, 0)] = visit[(x, y)] + 1


        # a -> b 옮기기
        if x <= b - y:
            if not visit.get((0, x + y)):
                queue.append((0, x + y))
                visit[(0, x + y)] = visit[(x, y)] + 1

        else:
            if not visit.get((x + y - b, b)):
                queue.append((x + y - b, b))
                visit[(x + y - b, b)] = visit[(x, y)] + 1


        # b -> a 옮기기
        if y<= a - x:
            if not visit.get((x + y, 0)):
                queue.append((x + y, 0))
                visit[(x + y, 0)] = visit[(x, y)] + 1

        else:
            if not visit.get((a, x + y - a)):
                queue.append((a, x + y - a))
                visit[(a, x + y - a)] = visit[(x, y)] + 1

        if visit.get((c, d)):
            if visit[(x, y)]>0:
                return (visit[(x, y)])

    return -1


print(bfs())