[백준2251&파이썬] BFS는 가지치기로 경우의 수를 구하기 적합하며 방문처리의 방법을 생각해보자

# 문제

백준 2251 물통 파이썬 풀이

2251번: 물통

# 코드

import copy
import sys
from collections import deque

A, B, C = map(int, sys.stdin.readline().split())
max_size = (A, B, C)
result = set()

# visit를 어떻게 처리할 것인가 ?
## 병이 똑같은 상태가 된다면 visit로 처리하는게 맞을듯 하다.
## 3차원 배열을 쓰는건 너무 메모리 낭비가 클까?

# 물을 붓는 행위 ( next ) 를 어떻게 할 것인가
# 종료조건은 무엇이 되는가 ?

visit = [[[False] * (C + 1) for _ in range(B + 1)] for _ in range(A + 1)]
# print(sys.getsizeof(visit)) # 사용하는 메모리 크기를 알아보기 위해서

dq = deque()
dq.append((0, 0, C))  # 마지막은 몇번째 순서인지 알기 위해서 사용
visit[0][0][C] = True  # 방문처리를 해준다
result.add(C)

while len(dq) != 0:
  cur = dq.popleft()

  for index, size in enumerate(cur):
    if size == 0:
      continue

    for other in range(3):
      if other == index:  # 자신을 제외한 다른 물통을 선택
        continue

      # 다른 물통이 가득찰때까지 물을 붓는 조건
      useage = max_size[other] - cur[other]
      next = copy.deepcopy(list(cur))  # tuple을 쓰면 변경이 안된다.
      next[other] += useage
      next[index] -= useage
      # ------------------------------

      # 물통의 용량이 0일될때까지 붓는 조건
      using_able = cur[index]
      next2 = copy.deepcopy(list(cur))  # tuple을 쓰면 변경이 안된다.
      next2[index] = 0
      next2[other] = cur[other] + using_able
      # ------------------------------

      if 0 <= next[0] <= max_size[0] and 0 <= next[1] <= max_size[1] and 0 <= next[2] <= max_size[2]:
        if visit[next[0]][next[1]][next[2]] == False:
          dq.append(next)
          visit[next[0]][next[1]][next[2]] = True
          if next[0] == 0 :
            result.add(next[2])
          # print(f"{cur} -> {next}")

      if 0 <= next2[0] <= max_size[0] and 0 <= next2[1] <= max_size[1] and 0 <= next2[2] <= max_size[2]:
        if visit[next2[0]][next2[1]][next2[2]] == False:
          dq.append(next2)
          visit[next2[0]][next2[1]][next2[2]] = True
          if next2[0] == 0:
            result.add(next2[2])
          # print(f"{cur} -> {next2}")

result = list(result)
result.sort()
print(*result)

 

# 풀이

• BFS를 이용해서 문제를 풀기로 했다. 가지치기 형식으로 여러 경우의 수에 조건에 맞는 것을 계속 구해야 하기 때문이다.

## 방문처리를 어떻게 할 것인가?

• A,B,C 물의 상태를 방문처리하기 위해서 visit[A][B][C]를 이용하는 3차원 배열을 만들었다.
• 최대 입력이 200 이기 때문에, 200 * 200 * 200 이 128MB을 만족시킬까 생각해봐야 한다.
• 3가지 물의 상태로 방문처리를 했다.

## 모든조건을 하나씩 손코딩하지말고, 반복문을 적극 활용하자

• 물통 3가지를 각각 선택하고, 다른 물통(2가지)에게 부어주는 경우의수 총 6가지가 나온다. 이걸 하나씩 손코딩하지말고 반복문을 이용해서 해결했다.

## 문제 출력조건을 잘 읽자

• 다 풀고 계속 오답이 나와서 왜그런가 했다. 
  • 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.
• 첫번째 물통이 비어있을 때 C를 출력해야 했다. 조건에 맞게 출력하니 잘 풀렸다.

## Set을 활용하자

• set이 result를 출력할때 중복조건을 신경쓰지 않아도 되는 점이 좋다.