📌문제
각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.
이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.
입력
첫째 줄에 세 정수 A, B, C가 주어진다.
출력
첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.
예제 입력
8 9 10예제 출력
1 2 8 9 10💡Idea
문제를 보고 DFS나 BFS를 이용해서 풀면 되겠다고 생각이 들기는 했지만, 그래프를 어떤 식으로 구성해야할지 고민을 많이 했었습니다.
이 문제는 물이 담겨있는 각 상태를 노드로 하고, 각 노드는 6개씩의 edge를 가진다고 가정하여 그래프를 구성하면 쉽게 풀리는 문제였습니다.
여기에서 6개의 edge는, 물🥛을 부울 수 있는 6가지 방법을 의미합니다.
- A에서 B로 붓기
- A에서 C로 붓기
- B에서 A로 붓기
- B에서 C로 붓기
- C에서 A로 붓기
- C에서 B로 붓기
위의 예제를 예로 들자면, 처음 C 물컵에는 10만큼의 물이 가득 차 있고 나머지 물컵들은 비어있기 때문에 노드는 [0, 0, 10]이 됩니다.
그리고 해당 상태에서 위의 6가지 방법으로 물을 부울 수 있기 때문에, 6가지의 edge를 따라 새로운 상태의 노드로 이동하는 그래프 탐색을 이어나가면 되됩니다.
💻코드
- ⏰ 시간 : 68 ms / 메모리 : 30948 KB
import sys
A, B, C = map(int, sys.stdin.readline().split())
visited = [[0 for _ in range(B + 1)] for _ in range(A + 1)]
def dfs(a, b):
if visited[a][b] == 0:
visited[a][b] = 1
c = C - a - b
# A -> B
if a + b < B: dfs(0, a + b)
else: dfs(a + b - B, B)
# A -> C
if a + c < C: dfs(0, b)
else: dfs(a + c - C, b)
# B -> A
if b + a < A: dfs(b + a, 0)
else: dfs(A, b + a - A)
# B -> C
if b + c < C: dfs(a, 0)
else: dfs(a, b + c - C)
# C -> A
if a + c < A: dfs(a + c, b)
else: dfs(A, b)
# C -> B
if b + c < B: dfs(a, b + c)
else: dfs(a, B)
dfs(0, 0)
ans = [C - i for i in range(B, -1, -1) if visited[0][i] == 1]
print(*ans)📝코드 설명
변수
visited: 이미 방문한 노드인지를 확인하는 이차원 배열입니다. 물컵의 개수는 3개이지만, A와 B 물컵에 담긴 양만 알고 있으면 C 물컵의 양은 저절로 결정이 되기 때문에 3차원 배열이 아닌 2차원 배열로도 표현할 수 있습니다.
visited[a][b]는 A 물컵에 a, B 물컵에 b, C 물컵에 C - a - b 만큼의 물이 들어있는 상태를 이미 방문했는가를 나타내며, 1이면 방문했음을, 0이면 아직 방문하지 않았음을 나타냅니다.
재귀 함수로 DFS를 구현하여 문제를 해결하였습니다.
이미 방문하지 않은 노드(세 물컵에 들어있는 물 양의 상태)라면, 해당 노드에서 갈 수 있는 6개의 경로를 확인하고 다시 dfs를 통해 경로를 이어서 탐색할 수 있도록 하였습니다.
