이번 문제는 BFS를 활용하여 해결하였다. a와 b의 범위가 100,000으로 매우 크기 때문에 방문처리 리스트를 2차원 리스트로 활용할 수 없었다. 그래서 set()으로 정의하고, (a, b) 형태로 담아 방문처리를 진행하였다. 세 종류의 작업의 모든 경우는 a를 채우는 경우, a를 비우는 경우, b를 채우는 경우, b를 채우는 경우, a를 b로 담는 경우, b를 a로 담는 경우 이렇게 총 6가지 경우였다. 이 모든 경우를 탐색할 수 있도록 하였다. a를 b로 담고, b를 a로 담는 경우를 깔끔하게 작성하기 위해 생각해보았고, a를 b로 담을 때의 a와 b의 다음 상태는 max(0, a-(B-b)), min(B, b+a) 로 정의할 수 있었다. 이 구문을 사용하여 코드를 잘 구현할 수 있었다.

Code

from collections import deque
a, b, c, d = map(int, input().split())
ca, cb = 0, 0
def bfs():
    q = deque()
    q.append((0, 0, 0))
    visited = set()
    visited.add((0, 0))
    while q:
        aa, bb, cnt = q.popleft()
        if (aa, bb) == (c, d):
            return cnt
        nxt_a, nxt_b = a, bb
        if 0 <= nxt_a < 100001 and 0 <= nxt_b < 100001 and (nxt_a, nxt_b) not in visited:
            visited.add((nxt_a, nxt_b))
            q.append((nxt_a, nxt_b, cnt+1))
        nxt_a, nxt_b = 0, bb
        if 0 <= nxt_a < 100001 and 0 <= nxt_b < 100001 and (nxt_a, nxt_b) not in visited:
            visited.add((nxt_a, nxt_b))
            q.append((nxt_a, nxt_b, cnt+1))
        nxt_a, nxt_b = aa, b
        if 0 <= nxt_a < 100001 and 0 <= nxt_b < 100001 and (nxt_a, nxt_b) not in visited:
            visited.add((nxt_a, nxt_b))
            q.append((nxt_a, nxt_b, cnt+1))
        nxt_a, nxt_b = aa, 0
        if 0 <= nxt_a < 100001 and 0 <= nxt_b < 100001 and (nxt_a, nxt_b) not in visited:
            visited.add((nxt_a, nxt_b))
            q.append((nxt_a, nxt_b, cnt+1))
        nxt_a, nxt_b = max(0, aa-(b-bb)), min(b, bb+aa)
        if 0 <= nxt_a < 100001 and 0 <= nxt_b < 100001 and (nxt_a, nxt_b) not in visited:
            visited.add((nxt_a, nxt_b))
            q.append((nxt_a, nxt_b, cnt+1))
        nxt_a, nxt_b = min(a, aa+bb), max(0, bb-(a-aa))
        if 0 <= nxt_a < 100001 and 0 <= nxt_b < 100001 and (nxt_a, nxt_b) not in visited:
            visited.add((nxt_a, nxt_b))
            q.append((nxt_a, nxt_b, cnt+1))
    return -1
print(bfs())