[G4] 백준 2251번 물통 C++ BFS, 완전 탐색

리뷰

 

https://www.acmicpc.net/problem/2251

세 물통의 상태를 체크하며 정답이 될 수 있는 모든 값에 대해 완전 탐색을 하는 문제

물통의 상태를 관리하는 부분이 DFS를 사용하는 것이 좀 더 직관적이고 편해보이긴하다.

 

 

전역 변수

• A : A물통의 최대 부피를 저장할 정수형 변수
• B : B물통의 최대 부피를 저장할 정수형 변수
• C : C물통의 최대 부피를 저장할 정수형 변수
• v : 각 물통에 물이 차있는 경우를 방문처리할 3차원 정수형 배열
• ans : 정답을 저장하기 위한 set자료구조
• Status : 시뮬레이션에 사용할 각 물통의 정보를 정의할 구조체

 

함수

1. bfs

void bfs()

 

너비 우선 탐색을 통해 각 물통의 상태를 시뮬레이션 하고 정답을 저장하기 위한 함수

1. Status타입의 큐 q를 초기화 해주고, A, B는 비고 C는 꽉 찬 상태를 push해준다.
2. 마찬가지로 A, B는 비고 C는 꽉 찬 상태에 방문 체크를 해준다.
3. 큐가 빌 때 까지 루프를 진행하고 매번 큐에 저장된 요소를 하나씩 빼내어 준다.
4. 현재 상태의 A, B, C물통에 담긴 물의 양을 정수형 변수 ca, cb, cc로 초기화 해준다.
5. 만약 ca가 빈 상태일 경우 cc의 값을 ans에 insert 해준다.
6. 이후 각 물통에서 다른 물통으로 물을 옮길 수 있는 상태일 경우 물을 옮기는 시뮬레이션을 진행해 준다.
7. 매번 시뮬레이션 시 A, B, C 물통의 상태가 방문체크가 되어있는지 확인을 해주어야 한다.
8. 만약 방문하지 않은 상태라면 방문 체크 후에 큐에 물통 정보를 추가해 주면 된다.

 

문제풀이

1. 변수 A, B, C에 각 물통의 최대 부피값을 입력 받아준다.
2. bfs함수를 호출하여 물을 옮기는 시뮬레이션을 진행해 준다.
3. ans에 저장된 값을 공백으로 구분하여 출력해 준다.

 

참고 사항

set자료구조를 사용하였으므로 오름 차순 정렬과 중복 문제는 걱정할 필요가 없다.

 

 

정답 코드

#include<iostream>
#include<queue>
#include<set>
using namespace std;

int A, B, C;
int v[201][201][201];
set<int> ans;
struct Status {
	int a, b, c;
};

void bfs() {
	queue<Status> q;
	q.push({ 0, 0, C });
	v[0][0][C] = 1;

	while (!q.empty()) {
		Status status = q.front(); q.pop();
		int ca = status.a, cb = status.b, cc = status.c;
		if (!ca) ans.insert(cc);

		if (ca) {
			if (cb != B) {
				int diff = min(ca, B - cb);
				if (!v[ca - diff][cb + diff][cc]) {
					v[ca - diff][cb + diff][cc] = 1;
					q.push({ ca - diff, cb + diff, cc });
				}
			}
			if (cc != C) {
				int diff = min(ca, C - cc);
				if (!v[ca - diff][cb][cc + diff]) {
					v[ca - diff][cb][cc + diff] = 1;
					q.push({ ca - diff, cb, cc + diff });
				}
			}
		}

		if (cb) {
			if (ca != A) {
				int diff = min(cb, A - ca);
				if (!v[ca + diff][cb - diff][cc]) {
					v[ca + diff][cb - diff][cc] = 1;
					q.push({ ca + diff, cb - diff, cc });
				}
			}
			if (cc != C) {
				int diff = min(cb, C - cc);
				if (!v[ca][cb - diff][cc + diff]) {
					v[ca][cb - diff][cc + diff] = 1;
					q.push({ ca, cb - diff, cc + diff });
				}
			}
		}

		if (cc) {
			if (ca != A) {
				int diff = min(cc, A - ca);
				if (!v[ca + diff][cb][cc - diff]) {
					v[ca + diff][cb][cc - diff] = 1;
					q.push({ ca + diff, cb, cc - diff });
				}
			}
			if (cb != B) {
				int diff = min(cc, B - cb);
				if (!v[ca][cb + diff][cc - diff]) {
					v[ca][cb + diff][cc - diff] = 1;
					q.push({ ca, cb + diff, cc - diff });
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> A >> B >> C;
	bfs();
	for (int i : ans) cout << i << " ";
}