백준[14867] 물통 (Python3)

독해력이 필요한 문제. 지문 분석을 잘못해 그리디로 생각해버렸다.
다른 물통에 물을 옮길 땐, 제한을 넘지 않는다면 '모두 옮겨야' 하는 건데, 일부만 넣을 수 있다고 이해해서 고생 좀 했다.

dp나 방문 처리를 해서 풀기엔 a, b의 범위의 최대 값이 100,000이기 때문에 메모리 초과가 발생한다. 이 방문 처리를 어떻게 할지 생각한 결과 set을 사용하기로 했다.

완전 탐색

다음 6가지에 대해 생각할 수 있다.

1. 물통 A를 가득 채운다. F(A)
2. 물통 B를 가득 채운다. F(B)
3. 물통 A를 비운다. E(A)
4. 물통 B를 비운다. E(B)
5. 물통 A의 물을 B로 옮긴다 M(A, B)
6. 물통 B의 물을 A로 옮긴다 M(B, A)

다만 5, 6의 경우 물을 '다 옮기면' 제한을 넘는지 확인할 필요가 있다.
이 사항들을 고려해 그대로 구현하면 AC를 받을 수 있다.

 

from collections import deque
maxA, maxB, dstA, dstB = map(int, input().split())

s = set()
q = deque([(0, 0, 0)])

ans = -1
while q:
    a, b, c = q.popleft()
    if a == dstA and b == dstB:
        ans = c
        break
    # 가득 채우기
    if (maxA, b) not in s:
        q.append((maxA, b, c + 1))
        s.add((maxA, b))
    if (a, maxB) not in s:
        q.append((a, maxB, c + 1))
        s.add((a, maxB))
    # 비우기
    if (0, b) not in s:
        q.append((0, b, c + 1))
        s.add((0, b))
    if (a, 0) not in s:
        q.append((a, 0, c + 1))
        s.add((a, 0))
    # 옮기기
    # a를 다 옮겨도 b의 목표를 채우지 못할 때
    if a < maxB - b:
        if (0, b + a) not in s:
            q.append((0, b + a, c + 1))
            s.add((0, b + a))
    # a를 일부만 옮기면 b의 목표를 채울 때
    else:
        temp = maxB - b
        if (a - temp, maxB) not in s:
            q.append((a - temp, maxB, c + 1))
            s.add((a - temp, maxB))
    # b를 다 옮겨도 a의 목표를 채우지 못할 때
    if b < maxA - a:
        if (a + b, 0) not in s:
            q.append((a + b, 0, c + 1))
            s.add((a + b, 0))
    # b를 일부만 옮기면 a의 목표를 채울 때
    else:
        temp = maxA - a
        if (maxA, b - temp) not in s:
            q.append((maxA, b - temp, c + 1))
            s.add((maxA, b - temp))
print(ans)