문제
각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.
이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.
입력
첫째 줄에 세 정수 A, B, C가 주어진다.
출력
첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.
예제 입출력
접근 및 코드1(실패)
실제로 코드를 작성하다가 실패한 방법이다.
(하다가 망해서 코드는 없다.)
다음과 같이 생각하고 진행했다.
- ABC 세 물통의 상태를 묶어서 노드로 생각하고, 인접 노드를 다른 물통에 물을 부어서 변한 상태라고 보면 그래프로 생각할수가 있다.
- 그래프로 봤기 때문에 bfs/dfs/ 탐색방법을 이용해서 원하는 노드를 찾을수 있다.
- 물을 옮길수 있는 경우의 수는 A->B,A->C, B->A,B->C, C->A,C->B로 6가지가 나온다.
- 또한 문제에서 물을 부을때 다 비워질때까지 쏟아붓는 경우, 또는 대상 물통이 꽉찰때까지 붓는 경우 두가지라고 했다.
- 따라서 4번의 규칙을 지키면서(물통이 넘치지 않게 하면서) 3번의 경우의 수롤 전부 인접노드로 만들어준다.
- 각 상태들을 dict의 key로 두어서 중복을 방지한다.(방문 처리)
- 또한 C의 값을 저장할 dict형을 하나 더 두어서 저장한다.
위와 같이 ABC를 별도로 저장하니까 생각할 경우의 수가 너무 많아져서 코드짜다 포기했다.
생각해보면, ab두개만 저장하면 전체에서 a+b값을빼면된다.
접근 및 코드2(최종)
문제접근
위에서 말한것 처럼, 각 물통의 상태를 노드로 생각한다.
물통의 상태는 a와b 두개만 저장하고, c의 경우에는 전체 - (a+b) 계산해준다.
이렇게 노드로 볼수 있으면, 그래프로 생각해서 탐색을 할수 있다.
그래프 탐색
탐색은 bfs이므로 큐를 만들고 매번 큐에서 노드를 꺼내고, 인접노드를 추가해주는 과정을 거친다.
인접노드의 경우, A->B, A->C, B->A, B->C, C->A, C->B 이렇게 6가지를 생각해줘야 된다.
그리고 중요한 것이 각 물통의 최대치는 200이라는 점을 고려해줘야 한다.
이렇게 인접노드를 추가할수 있으면, 일반적인 bfs와 다를것이 없다.
중요한 점은 a물통이 비었을때 c의 물의 양을 구하는 것이 문제이므로, 큐에서 노드를 꺼낼때 마다, a의 값이 0인지 확인하고, 0일때의 c물통의 값을 구해서 따로 저장해준다.
이 c물통의 물의 양의 경우, 중복될수 있기 때문에(같은 양이 여러번 나올수 있음) set 자료구조를 이용해서, 중복을 제거해주었다.
최종적으로, 저장한 물의 양들을 출력 형식에 맞춰서 출력해주었다.
코드는 다음과 같다.
인접노드를 구현한 부분에 주석을 달아놓았으니 어렵지 않게 이해할수 있다.
import sys
from collections import deque
'''입력'''
a,b,c = map(int,sys.stdin.readline().split())
#시작노드 만들기 - 시작은 0,0이 비어있음
start_node = (0,0)
#방문처리츨 할 딕셔너리
visited = dict()
#방문확인을 6번씩 해야되므로 따로 함수로 분리 - True면 방문안해서 추가함, False면 이미 방문한 노드
def check(node:tuple) -> bool:
if node not in visited:
visited[node] = 1
return True
else:
return False
#bfs 함수 정의 - 노드를 딕셔너리에 키로 저장해야되기 때문에 튜플로 한다.,water_count를 반환한다.
def bfs(start_node:tuple,water_total:int) -> set:
#C의 값 저장 - A가 0일때만 저장, set으로 만들어서 중복데이터저장을 방지
water_count = set()
#방문이 필요한 노드를 넣을 큐
need_visited = deque(list())
#시작노드를 방문이 필요한 노드에 넣음 - A가 0일떄만 방문처리
need_visited.append(start_node)
while need_visited:
#방문해야될 노드를 꺼냄
current_a,current_b = need_visited.popleft()
current_c = water_total - (current_a+current_b)
'''인접노드를 만듦 - 6가지 경우,최대치 생각해줘야됨.'''
#A->B A->C B->A B->C C->A C->B
#1. 현재노드의 a가 0이면 c의 값을 저장
if current_a == 0:
water_count.add(water_total - (current_a+current_b))
#2. A->B일때
#물의 양을 체크함 -> 전부 부을수 있는지 없는지
#옮길수 있는 물의양
move_amount_of_water = min(current_a,b-current_b)
temp_node = (current_a - move_amount_of_water,current_b + move_amount_of_water)
if check(temp_node) == True:
need_visited.append(temp_node)
#3. A->C일때
move_amount_of_water = min(current_a,c - current_c)
temp_node = (current_a - move_amount_of_water,current_b)
if check(temp_node) == True:
need_visited.append(temp_node)
#4. B->A일때
move_amount_of_water = min(current_b,a-current_a)
temp_node = (current_a + move_amount_of_water,current_b - move_amount_of_water)
if check(temp_node) == True:
need_visited.append(temp_node)
#5. B->C일때
move_amount_of_water = min(current_b,c-current_c)
temp_node = (current_a,current_b - move_amount_of_water)
if check(temp_node) == True:
need_visited.append(temp_node)
#6. C->A일때
move_amount_of_water = min(current_c,a-current_a)
temp_node = (current_a + move_amount_of_water,current_b)
if check(temp_node) == True:
need_visited.append(temp_node)
#7. C->B일때
move_amount_of_water = min(current_c,b-current_b)
temp_node = (current_a,current_b + move_amount_of_water)
if check(temp_node) == True:
need_visited.append(temp_node)
return water_count
result = sorted(list(bfs(start_node,c)))
print(' '.join(list(map(str,result))))결과
