[파이썬/Python] 백준 2251번: 물통

숨·2024년 8월 12일

코테

알고리즘 문제 풀이

목록 보기

48/105

📌 문제 : 백준 2251번

📌 문제 탐색하기

A, B, C : 3개의 물통 용량 ( $1≤A, B, C≤200$ )

✅ 입력
1. A, B, C 입력
✅ 출력
1. C에 담겨져 있는 물 양의 모든 경우의 수 출력
2. 경우의 수 오름차순 정렬

용량이 A인 첫 번째 물통이 비어 있을 때, 용량이 C인 세 번째 물통에 담겨 있을 수 있는 모든 물의 양을 구해내는 문제이다.

문제의 조건
1. 각 물통의 시작 상태 = (0, 0, C)
2. 어떤 물통에 들어있는 물 → 다른 물통에 쏟아 부을 수 있다.
3. 한 물통이 빈 상태 / 가득 찬 상태 까지 물 부을 수 있다.
4. 사라지는 물 ❌

6가지의 물을 옮기는 방법이 있다.
1) A → B
2) A → C
3) B → A
4) B → C
5) C → A
6) C → B

문제의 조건 3에 의해 한번 물을 부을 때,
1) 물이 들어있던 물통의 물이 0
2) 물이 들어오는 물통의 물이 가득 참
이 2가지 경우에만 물 붓는 것을 멈출 수 있다.
따라서 물을 옮길 때, 한 물통의 물을 전부 부어도 다른 물통이 넘치지 않는 경우를 찾아서 물의 양을 구해주어야 한다.

6가지 방법을 진행했을 때 3개의 물통에 담을 수 있는 경우의 수를 모두 구하고, [A][B][C] 형식으로 접근할 수 있는 3차원 배열 방문 리스트에 방문 처리 해준다.
→ 이미 만든 경우의 수인지 확인하기 위함이다.

그 중 A 물병의 물이 0일 때의 C 물 양을 저장해준다.
이 때, 동일한 경우를 제외하기 위해 set() 자료형에 저장하면 좋을 것 같다.

BFS를 통해 위와 같은 물을 옮기는 과정을 반복하면서 모든 C의 물 양 경우들을 얻는다.

가능한 시간복잡도

전체 물통의 경우의 수 → $O((A+1)*(B+1)*(C+1))$
6가지 방법이 있는 BFS 수행 → $O(6*(A+1)*(B+1)*(C+1))$

최종 시간복잡도
$O((A+1)*(B+1)*(C+1))$
최악의 경우 $O(201^3) = O(8,120,601)$ 이 되는데
이는 2초 내에 연산이 가능하다.

알고리즘 선택

BFS로 물통의 양의 모든 경우의 수 구해서 원하는 정답 찾기

📌 코드 설계하기

BFS 구현
A, B, C 입력
BFS 실행
결과 출력

📌 시도 회차 수정 사항

1회차

처음에 3. 한 물통이 빈 상태 / 가득 찬 상태 까지 물 부을 수 있다.라는 조건을 이해하지 못해서 각 물통의 물을 1씩 감소, 증가하는 식으로 구현하려고 해서 이상한 답을 얻었다.

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline


# bfs 구현
def bfs():
    # 큐 정의
    queue = deque()
    # 초기값 입력
    queue.append((0, 0, C))
    # 방문 리스트 초기화
    visited = [[[0] * (C + 1) for _ in range(B + 1)] for _ in range(A + 1)]
    # 방문 처리
    visited[0][0][C] = 1
    # 결과 저장
    answer = set()

    while queue:
        a, b, c = queue.popleft()

        # 원하는 경우 찾았을 때 저장
        if a == 0:
            answer.add(c)

        # 물 옮기는 모든 경우 구하기 (한 물통 0 또는 다른 물통 가득)
        # 1) A → B
        if a + b > B:
            new_a, new_b = a - (B - b), B
        else:
            new_a, new_b = 0, b + a
        if not visited[new_a][new_b][c]:
            # 방문 처리
            visited[new_a][new_b][c] = 1
            # 큐에 넣기
            queue.append((new_a, new_b, c))

        # 2) A → C
        if a + c > C:
            new_a, new_c = a - (C - c), C
        else:
            new_a, new_c = 0, c + a
        if not visited[new_a][b][new_c]:
            # 방문 처리
            visited[new_a][b][new_c] = 1
            # 큐에 넣기
            queue.append((new_a, b, new_c))

        # 3) B → A
        if b + a > A:
            new_b, new_a = b - (A - a), A
        else:
            new_b, new_a = 0, b + a
        if not visited[new_a][new_b][c]:
            # 방문 처리
            visited[new_a][new_b][c] = 1
            # 큐에 넣기
            queue.append((new_a, new_b, c))

        # 4) B → C
        if b + c > C:
            new_b, new_c = b - (C - c), C
        else:
            new_b, new_c = 0, c + b
        if not visited[a][new_b][new_c]:
            # 방문 처리
            visited[a][new_b][new_c] = 1
            # 큐에 넣기
            queue.append((a, new_b, new_c))

        # 5) C → A
        if c + a > A:
            new_c, new_a = c - (A - a), A
        else:
            new_c, new_a = 0, a + c
        if not visited[new_a][b][new_c]:
            # 방문 처리
            visited[new_a][b][new_c] = 1
            # 큐에 넣기
            queue.append((new_a, b, new_c))

        # 6) C → B
        if c + b > B:
            new_c, new_b = c - (B - b), B
        else:
            new_c, new_b = 0, b + c
        if not visited[a][new_b][new_c]:
            # 방문 처리
            visited[a][new_b][new_c] = 1
            # 큐에 넣기
            queue.append((a, new_b, new_c))

    # 오름 차순 정렬해 반환
    return sorted(answer)


# A, B, C 입력
A, B, C = map(int, input().split())

# bfs 수행
answer = bfs()

# 결과 출력
print(' '.join(map(str, answer)))