문제

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

www.acmicpc.net/problem/2251

  • 입력

첫째 줄에 세 정수 A, B, C가 주어진다.

  • 출력

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

과정

우선 설명 전에! 문제풀면서 헷갈렸던 건데 여기서 원하는 답은 첫 번째 물통이 비어있을 때 세 번째 물통에 담겨있을 수 있는 물의 양을 모두 구하는 것이라는 걸 잊지 말자.

처음엔 세 번째 물통에 담겨있을 수 있는 물의 양이 집합으로 선언했다. 계속 집합에 넣으면서 중복되는 값이 들어갈 수도 있다고 생각했기 때문이다(사실은 중복되는 값이 들어갈 일 없음). 그리고 방문을 처리하기 위한 배열도 3차원으로 선언해서 좀 더 비효율적인 코드이다. 그래도 통과는 했다.

코드를 간단히 설명하자면 bfs를 돌면서 물을 옮길 수 있는 6가지 경우의 수를 모두 고려한다. i번째 물통에서 j번째 물통으로 물을 붓고 만약 첫 번째 물통이 비어있다면 세 번째 물통의 용량을 저장해야 하는 과정을 계속 반복하는 것이다.

검색해보니까 많은 사람들이 6가지 경우를 조건문으로 나눠서 풀었던데 나는 반복문을 통해 구했다. 그냥 보면 복잡해보이지만 사실 별 거 없다. 그냥 물통 A에서 물통 B로 물 옮기는 걸 생각하면 됨. 자세한 건 코드를 통해 확인하자.

import sys
from collections import deque

def bfs():
    global bottle
    q = deque()
    # a, b, c 물통의 물의 양, c 물통에 담길 수 있는 물의 양 집합
    q.append([[0, 0, bottle[2]], set({bottle[2]})])
    # a, b, c 물의 양에 따른 방문 처리를 위한 3차원 배열
    visit = [[[False]*(bottle[2]+1) for _ in range(bottle[1]+1)] for _ in range(bottle[0]+1)]
    visit[0][0][bottle[2]] = True

    while q:
        now, cSet = q.popleft()

        # i -> j번째 통으로 물을 옮기는 6가지 경우의 수
        for i, j in zip([0, 1, 0, 2, 1, 2], [1, 0, 2, 0, 2, 1]):
            new = [now[0], now[1], now[2]]
            tmp = now[i] + now[j]
            new[j] = tmp if tmp <= bottle[j] else bottle[j]
            new[i] = 0 if tmp <= bottle[j] else tmp - bottle[j]

            if visit[new[0]][new[1]][new[2]] == False:
                visit[new[0]][new[1]][new[2]] = True
                # a 물통이 비어있다면 c 물통의 물의 양을 저장
                if new[0] == 0:
                    cSet.add(new[2])
                q.append([new, cSet])
    return cSet

bottle = list(map(int, sys.stdin.readline().split()))
res = sorted(list(bfs()))
print(*res)

최종코드

처음으로 구현한 코드도 맞았지만 최적화가 너무 덜 되어 있어서 아래와 같이 수정했다.

  1. 세 번째 물통에 담길 수 있는 물의 양은 중복으로 들어오지 않는다. 그래서 집합에서 리스트로 수정했다.
  2. 첫 번째, 두 번째 물통에 담긴 물의 양에 따라 세 번째 물통의 물의 양이 정해진다. 따라서 배열을 굳이 3차원으로 선언하지 않아도 된다. 2차원 배열로 수정했다.
import sys
from collections import deque

def bfs():
    global bottle
    q = deque()
    # a, b, c 물통의 물의 양, c 물통에 담길 수 있는 물의 양 리스트
    q.append([[0, 0, bottle[2]], [bottle[2]]])
    # a, b 물통의 물의 양에 따라 c 물통의 양은 정해져있으므로 2차원 배열로 설정함
    visit = [[False]*(bottle[1]+1) for _ in range(bottle[0]+1)]
    visit[0][0] = True

    while q:
        now, arr = q.popleft()

        # i -> j번째 통으로 물을 옮기는 6가지 경우의 수
        for i, j in zip([0, 1, 0, 2, 1, 2], [1, 0, 2, 0, 2, 1]):
            new = [now[0], now[1], now[2]]
            tmp = now[i] + now[j]
            # j번째 물통이 넘치지 않는 경우 j = now[j] + now[i], i = 0
            # j번째 물통이 넘치는 경우 j = bottle[j], i = now[j] + now[i] - bottle[j]
            new[j] = tmp if tmp <= bottle[j] else bottle[j]
            new[i] = 0 if tmp <= bottle[j] else tmp - bottle[j]

            if visit[new[0]][new[1]] == False:
                visit[new[0]][new[1]] = True
                # a 물통이 비어있다면 c 물통의 물의 양을 저장
                if new[0] == 0:
                    arr.append(new[2])
                q.append([new, arr])
    return arr

bottle = list(map(int, sys.stdin.readline().split()))
res = sorted(bfs())
print(*res)

참고 사이트