[Python] 14867 - 물통 (골드3)

1. 문제 설명

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

14867번: 물통

내가 풀 당시에는 골드2였는데 등급이 강등되었다.

 

---

2. 아이디어

그래프 문제라고 생각하면 쉽다.

현재 위치에서 a에 물을 채우는 경우와 b에 물을 채우는 경우로 분기점을 나누고,

a의 물을 버리는 경우와 b의 물을 비우는 경우의 분기점을 모두 큐에 넣는다.

그리고 a에서 b에 물을 넣는 경우와 b에서 a에 물을 넣는 경우를 고려해주면 된다.

 

그리고 한 번이라도 거친 지점은 방문처리 해주면 되는데,

"아니, a의 물을 b에 옮겼다가 다시 a에 물을 떠주는 등 똑같은 지점에 다시 돌아오게 될 수도 있는 거 아니냐?"라고

생각할 수도 있지만 사실은 그렇지 않다.

a와 b에 들어있는 물의 양이 똑같은 지점으로 회귀했다는 건 제자리 걸음을 했다는 것과 같은 의미기 때문.

같은 상태로 회귀했다는 것부터 이미 고려할 대상이 아님을 의미한다.

따라서 위의 조건에 따라 bfs를 구현하면 끝난다.

 

주의할 점이 있다면 visited를 이차원 리스트로 구현하는 순간 메모리 초과로 터진다.

10만 이차원 배열이면 100억 * 4byte = 38146.97264MB이므로 메모리 제한을 거뜬히 씹어먹어버린다.

나는 그래서 빈 딕셔너리를 하나 만들고 (a, b) = 이동횟수 라는 값을 넣어주었다.

조회했을 때, 값이 존재하지 않거나, 이동횟수가 0인 시점이면 이동하는 식으로 구현하면

굳이 이차원 리스트를 만들 이유가 없어지므로 이슈가 해결된다.

 

---

3. 코드

import sys
from collections import deque

input = sys.stdin.readline

def bfs(a, b, c, d):
    queue = deque()
    queue.append([0, 0])
    visited = {}
    visited[(0, 0)] = 0
    
    if c == 0 and d == 0:
        return 0

    while queue:
        y, x = queue.popleft()
        if visited.get((c, d)):
            return visited.get((c, d))

        if not visited.get((a, x)): # a 채우기
            visited[(a, x)] = visited[(y, x)] + 1
            queue.append([a, x])
        if not visited.get((y, b)): # b 채우기
            visited[(y, b)] = visited[(y, x)] + 1
            queue.append([y, b])
        if not visited.get((0, x)): # a 버리기
            visited[(0, x)] = visited[(y, x)] + 1
            queue.append([0, x])
        if not visited.get((y, 0)): # b 버리기
            visited[(y, 0)] = visited[(y, x)] + 1
            queue.append([y, 0])

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

    return -1

def solution():
    a, b, c, d = map(int, input().split())
    print(bfs(a, b, c, d))

solution()