[백준알고리즘] 2251번: 물통 -Python

[백준알고리즘] 2251번: 물통 -Python

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

2251번: 물통

이번 문제에서도 visit을 딕셔너리로 사용했다. 그리고 (A, B, C)에 존재하는 물의 양을 튜플로 묶어서 키로 다루었다.

 

다른 분들의 코드를 보니 visit을 그냥 리스트로 사용하신 분들이 대부분이셨다. 전체 물의 양은 C로 고정이기 때문에 A와 B만 알고 있어도 C는 정해지기 때문이다.

 

그리고 각각의 상황에 맞게 조건문들을 걸어주었다. A->B로 물을 옮길 수 있는 경우, A->C로 물을 옮길 수 있는 경우.... C->B로 물을 옮길 수 있는 경우 모두 고려해 주었고, BFS 방식으로 모든 경우를 찾아주었다.

 

import sys
from collections import deque

def solve():
    global res
    queue = deque([start])
    visited = {start:1}

    while queue:
        qa, qb, qc = queue.popleft()
        if qa == 0:
            res.add(qc)

        # a->
        if qa > 0:
            if qb < b: # a->b
                t = qa + qb
                if t <= b and not visited.get((0, t, qc)):
                    visited[(0, t, qc)] = 1
                    queue.append((0, t, qc))
                elif t > b and not visited.get((t-b, b, qc)):
                    visited[(t-b, b, qc)] = 1
                    queue.append((t-b, b, qc))
            if qc < c: # a->c
                t = qa + qc
                if t <= c and not visited.get((0, qb, t)):
                    visited[(0, qb, t)] = 1
                    queue.append((0, qb, t))
                elif t > c and not visited.get((t-c, qb, c)):
                    visited[(t-c, qb, c)] = 1
                    queue.append((t-b, qb, c))
    
        # b->
        if qb > 0:
            if qa < a: # b->a
                t = qa + qb
                if t <= a and not visited.get((t, 0, qc)):
                    visited[(t, 0, qc)] = 1
                    queue.append((t, 0, qc))
                elif t > a and not visited.get((a, t-a, qc)):
                    visited[(a, t-a, qc)] = 1
                    queue.append((a, t-a, qc))
            if qc < c: # b->c
                t = qb + qc
                if t <= c and not visited.get((qa, 0, t)):
                    visited[(qa, 0, t)] = 1
                    queue.append((qa, 0, t))
                elif t > c and not visited.get((qa, t-c, c)):
                    visited[(qa, t-c, c)] = 1
                    queue.append((qa, t-c, c))

        # c->
        if qc > 0:
            if qa < a: # c->a
                t = qa + qc
                if t <= a and not visited.get((t, qb, 0)):
                    visited[(t, qb, 0)] = 1
                    queue.append((t, qb, 0))
                elif t > a and not visited.get((a, qb, t-a)): 
                    visited[(a, qb, t-a)] = 1
                    queue.append((a, qb, t-a))
            if qb < b: # c->b
                t = qb + qc
                if t <= b and not visited.get((qa, t, 0)):
                    visited[(qa, t, 0)] = 1
                    queue.append((qa, t, 0))
                elif t > b and not visited.get((qa, b, t-b)):
                    visited[(qa, b, t-b)] = 1
                    queue.append((qa, b, t-b))

a, b, c = map(int, sys.stdin.readline().split())
start = (0, 0, c)
res = set()

solve()
res = sorted(list(res))
for r in res:
    sys.stdout.write("{} ".format(r))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다