[python] 백준 - 2251. 물통

🤔문제 해결

1. S1 | 그래프 이론, 그래프 탐색, BFS

2. 물통이 3개지만 물의 총량이 고정이기 때문에 a,b 두 물통만 체크하면 된다. c는 저절로 정해짐.

3. visited 리스트를 2중 리스트로 작성한다.( 변수가 2개이기 때문 )

4. 처음 0,0을 넣고 BFS를 한다.       

 (1) a 물통이 0일 때 c 물통의 양을 답리스트에 넣어준다. 

 (2) a -> b, a -> c, b -> a, b -> c, c -> a, c -> b 6가지를 모두 탐색한다.

 (3) 조건에 맞다면 물을 나누고 계속 탐색한다.

5. 답을 출력조건에 맞게 출력하면 끝.

 

💨 변수를 2개만 정해서 visited를 2중리스트로 하는 것과 물을 옮기는 경우를 생각해보자

 

💻소스 코드

from collections import deque


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


def bfs():
    q.append((0,0))  # 처음 물통 a,b는 0,0
    visited[0][0] = 1
    while q:
        x, y = q.popleft()
        z = c - x - y  # z는 a와b에 의해 결정된다.
        if x == 0:  # 조건에서 a물통이 0일때 이므로
            answer.append(z)

        # a에서 b 물을 옮기는 경우
        if x > 0 and y < b:  # a에 물이 있고 b에 물이 가득차있지 않을 때
            w = min(x, b - y)
            pour(x - w, y + w)
        # a에서 c
        if x > 0 and z < c:
            w = min(x, c - z)
            pour(x - w, y)

        # b에서 a
        if y > 0 and x < a:
            w = min(y, a - x)
            pour(x + w, y - w)
        # b에서 c
        if y > 0 and z < c:
            w = min(y, c - z)
            pour(x, y - w)

        # c에서 a
        if z > 0 and x < a:
            w = min(z, a - x)
            pour(x + w, y)
        # c에서 b
        if z > 0 and y < b:
            w = min(z, b - y)
            pour(x, y + w)


if __name__ == "__main__":
    a, b, c = map(int, input().split())
    # visited: a 물통과 b 물통의 양에 따라 c 물통의 양이 정해지기 때문에
    # a,b 두 통을 실행한 적이 있는지 확인하는 2중리스트
    visited = [[0] * (b + 1) for _ in range(a + 1)]
    # 답을 넣을 배열
    answer = []
    # BFS
    q = deque()
    bfs()
    # 답 출력
    answer.sort()
    print(' '.join(list(map(str, answer))))

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

2251번: 물통

---

---

---

문제

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

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

입력

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

출력

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