[백준문제풀이] 2251 물통

 

풀이일시 : 2020-11-13

​

 

문제 :

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

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

​

​

입력 :

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

ex)

8 9 10

​

​

출력 :

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

ex)

1 2 8 9 10

​

​

풀이 :

A가 비었을때 세번째 물통에 있을 수 있는 물의 양을 모두 구해내라.

한 물통이 비거나 다른 한 물통이 가득찰 때까지 물을 부을 수 있다는 조건을 BFS로 활용. 전체 탐색하면서 push

 

dbstndi6316.tistory.com/63

[기본문제풀이] BFS 너비우선탐색

#include <iostream>
#include <algorithm> //sort 쓰기위함
#include <queue>

using namespace std;

struct Data {
	int a, b, c;
};

int A, B, C; //최대치
bool chk[202][202], ans[202];

void bfs() {
	queue <Data> q;
	q.push({ 0,0,C });
	while (!q.empty()) {
		Data now = q.front();
		q.pop();

		//이미 확인한 것이라면 다음 while문으로 가서 확인
		if (chk[now.a][now.b])
			continue;

		chk[now.a][now.b] = true;

		if (now.a == 0) //a가 0일때 출력해준다.
			ans[now.c] = true;

		//옮기는 경우의 수는 총 6개 반복 a->b a->c b->a b->c c->a c->b

		//a->b
		/*현재 a에 담겨있는양 + 현재 b에 담겨있는 양이
		입력값 B보다 큰 경우 B물통은 최대용량만큼
		물이 가득 채워지게 되고, A물통은 현재 a양 +현재 b양 -최대용량 만큼
		물이 남게 된다. */
		if (now.a + now.b > B)
			q.push({ (now.a + now.b) - B,B,now.c });

		//현재 a + 현재 b 용량이 B보다 작은 경우
		/* A물통에서 물이 전부 옮겨지므로 A는 0
		B는 현재 a+ 현재 b 용량이 된다.
		C는 변화가 없으므로 현재 용량 now.c를 넣어준다. */
		else
			q.push({ 0,now.a + now.b,now.c });

		//a->c
		if (now.a + now.c > C)
			q.push({ (now.a + now.b) - C,now.b,C });
		else
			q.push({ 0,now.b,now.a + now.c });

		//b->a
		if (now.b + now.a > A)
			q.push({ A,(now.b + now.a) - A,now.c });
		else
			q.push({ now.b + now.a, 0, now.c });

		//b->c
		if (now.b + now.c > C)
			q.push({ now.a,(now.b + now.c) - C,C });
		else
			q.push({ now.a, 0, now.b + now.c });

		//c->a
		if (now.c + now.a > A)
			q.push({ A,now.b,(now.c + now.a) - A });
		else
			q.push({ now.c + now.a,now.b,0 });

		//c->b
		if (now.c + now.b > B)
			q.push({ now.a,B,(now.c + now.b) - B });
		else
			q.push({ now.a,now.c + now.b,0 });
	}

}

void print() {
	for (int i = 0; i <= C; i++) {
		if (ans[i])
			printf("%d ", i);
	}
}

int main() {
	cin >> A >> B >> C; //C는 꽉 차있는것 A,B는 비어있다.
	bfs();
	print();
	return 0;
}