[ 백준-2251번 / BFS ] 물통

1. 문제

---

 

문제보기

문제

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

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

입력

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

출력

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

예제 입력 1 복사

8 9 10

예제 출력 1 복사

1 2 8 9 10

 

2. 소스코드

---

- 갈피를 못잡았던 문제. 완전 탐색인 것 같은데, 처음과 끝을 어떻게 잡아야할지 감을 못잡았었다.

- 그러나 조금 생각해보니, 결국 가장 빨리 잡는 경우를 구하는 술래잡기 문제랑 비슷했다. 

- 따라서, 현 status에서 가능한 모든 경우의 수를 que에 넣고, 방문여부를 check한다. 결국 BFS문제.

- 방문여부 체크는 a,b의 무게를 이용한 2차원 배열을 사용했다. a,b의 무게에 따라 c의 무게는 자동으로 결정되기 때문.

- 천천히 생각하면 금방 풀 수 있는 문제인데, 조금 오래 걸렸다.

 

소스코드

#include <cstdio>
#include <queue>
#define MAX 200 
using namespace std;

int sizeA, sizeB, sizeC;
int a, b, c;
bool check[MAX+1];
bool visited[MAX+1][MAX+1];

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

void bfs() {
	queue<Cup> que;
	que.push({ 0,0,sizeC });
	while (!que.empty())
	{
		auto cur = que.front(); que.pop();
		int a = cur.a;
		int b = cur.b;
		int c = cur.c;
		
		if (visited[a][b]) continue;
		visited[a][b] = true;
		if(a == 0) check[c] = true;

		//1) a->b
		if (a + b > sizeB) que.push({ a + b - sizeB, sizeB, c });
		else que.push({ 0, a + b, c });

		// 2) a=>c
		if (a + c > sizeC) que.push({ a + c - sizeC, b, sizeC });
		else que.push({ 0, b, a + c });

		// 3) b => a
		if (b + a > sizeA) que.push({ sizeA, b + a - sizeA, c });
		else que.push({ b + a, 0, c });

		// 4) b => c
		if (b + c > sizeC) que.push({ a, b + c - sizeC, sizeC });
		else que.push({ a, 0, b + c });

		// 5) c => a
		if (c + a > sizeA) que.push({ sizeA, b, c + a - sizeA });
		else que.push({ c + a, b, 0 });

		// 6) c => b
		if (c + b > sizeB) que.push({ a, sizeB, c + b - sizeB });
		else que.push({ a, c + b, 0});

	}

	return;
}

int main() {
 
	scanf("%d %d %d", &sizeA, &sizeB, &sizeC);
 
	bfs();
	for (int i = 0; i <= MAX; ++i) {
		if (check[i])
			printf("%d ", i);
	}
	printf("\n");

	return 0;
}