[실버1] 2251번 : 물통

🛠 문제

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

👩🏻‍💻 해결 방법

처음에는 dfs로 풀기 위해 생각했으나 bfs로 문제를 해결할 수 있었다
3가지 밖에 없어서 모든 경우의 수를 다 구현해 주었다
물통이 이동 가능하면 pour 함수를 사용해 visit 체크를 해주었다
a 물통이 비어있을 때 c 물통의 용량을 구해야 하므로 x(a)가 0일때 z(c)를 추가해주었다

소스 코드

from collections import deque

def pour(x, y):
  if not visit[x][y]:
    visit[x][y] = 1
    q.append((x, y))

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

  while q:
    x, y = q.popleft()
    z = c - x - y
    # a 물통이 비어있을 때
    if x == 0:
      answer.append(z)
    
    if x > 0 and y < b:  # a->b
      w = min(x, b-y)
      pour(x-w, y+w)
    if x > 0 and z < c:  # a->c
      w = min(x, c-z)
      pour(x-w, y)
    if y > 0 and x < a:  # b->a
      w = min(y, a-x)
      pour(x+w, y-w)
    if y > 0 and z < c:  # b->c
      w = min(y, c-z)
      pour(x, y-w)
    if z > 0 and x < a:  # c->a
      w = min(z, a-x)
      pour(x+w, y)
    if z > 0 and y < b:  # c->b
      w = min(z, b-y)
      pour(x, y+w)

a, b, c = map(int, input().split())
# a,b 물통 실행 확인(c는 a,b 물통의 양에 따라 정해짐)
visit = [[0] * (b+1) for _ in range(a+1)]

answer = []
q = deque()
bfs()

answer.sort()
print(' '.join(list(map(str, answer))))