[C++] 백준 2251: 물통

문제

[C++] 백준 2251: 물통 GOLD 4
https://www.acmicpc.net/problem/2251

 

---

 

접근 방법

이 문제의 핵심은 상태를 그래프로 보고 BFS로 탐색하는 문제이다.
각 물통의 상태를 하나의 노드로 보고, 물을 옮기는 행위를 간선으로 생각하면 된다.

 

처음에는 세 물통 A, B, C의 상태 (A, B, C)를 모두 고려해야 할 것 같지만,
전체 물의 양이 항상 일정하기 때문에 다음과 같이 단순화할 수 있다.

• 전체 물의 양 = 항상 C의 초기값
• 따라서 C = 전체 - A - B로 계산 가능

즉, (A, B)만 알면 상태를 완전히 표현할 수 있기 때문에 visited[A][B] 형태로 방문 체크를 진행한다.

탐색은 BFS를 사용하여 가능한 모든 상태를 순회하며, 그 중에서 A가 0인 상태일 때의 C값만 정답으로 저장하면 된다.

 

상세 아이디어

1. 상태 정의

 

• 상태: (A, B)
• C는 C = now[2] - A - B로 계산
  • 총 물의 양 - A - B = C

 

 

2. 가능한 이동 경우

물통이 3개이므로, 한 번의 행동은 한 물통에서 다른 물통으로 물을 붓는 것뿐이다.

가능한 경우는 총 6가지:

• A → B
• A → C
• B → A
• B → C
• C → A
• C → B

이를 반복문으로 처리하기 위해 다음과 같이 배열로 정의한다.

int send[6] = { 0,0,1,1,2,2 };
int recv[6] = { 1,2,0,2,0,1 };

각 i에 대해 send[i] → recv[i]로 물을 이동시키는 의미이다.

 

3. 상태 전이 (물 붓기)

현재 상태를 next 배열로 복사한 뒤, 물을 이동시킨다.

int next[3] = { A, B, C };
next[recv[i]] += next[send[i]];
next[send[i]] = 0;

 

이후, 받는 물통이 넘치는 경우를 처리한다.

if (next[recv[i]] > now[recv[i]]) {
    next[send[i]] = next[recv[i]] - now[recv[i]];
    next[recv[i]] = now[recv[i]];
}

 

4. BFS 탐색

• 초기 상태: (0, 0, C)
• 큐를 이용해 상태를 하나씩 꺼내면서
• 6가지 이동을 모두 적용하여 다음 상태 생성

방문하지 않은 상태라면 큐에 추가한다.

if (!visited[next[0]][next[1]]) {
    visited[next[0]][next[1]] = true;
    q.push({next[0], next[1]});
}

 

5. 정답 저장

문제 조건에 따라 A가 0일 때의 C값만 저장한다.

if (next[0] == 0)
    ans.push_back(next[2]);

 

탐색이 끝난 후 sort 함수를 이용하여 오름차순으로 정렬하여 출력한다.

 

구현 시 주의할 점

• 중복 정답 처리:
  • 같은 C 값이 여러 번 나올 수 있으므로 아래 방법 중 하나로 처리해야 한다. 
    • vector 사용 시 → 마지막에 sort
    • 또는 bool ans[] 배열 사용

 

---

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int send[6] = { 0,0,1,1,2,2 };
int recv[6] = { 1,2,0,2,0,1 };
int now[3];
bool visited[201][201];
vector<int> ans;

void BFS()
{
	queue<pair<int, int>> q;
	q.push(make_pair(0, 0));
	visited[0][0] = true;
	ans.push_back(now[2]);

	while (!q.empty())
	{
		pair<int, int> p = q.front();
		q.pop();
		
		int A = p.first, B = p.second,
			C = now[2] - A - B;

		for (int i = 0; i < 6; i++)
		{
			int next[3] = { A,B,C };
			next[recv[i]] += next[send[i]];
			next[send[i]] = 0;

			// 받은 물통의 양이 용량을 넘길 때
			if (next[recv[i]] > now[recv[i]])
			{
				next[send[i]] = next[recv[i]] - now[recv[i]];
				next[recv[i]] = now[recv[i]];
			}
			// A와 B의 물의 양을 통해 방문 배열 체크
			if (!visited[next[0]][next[1]])
			{
				visited[next[0]][next[1]] = true;
				q.push(make_pair(next[0], next[1]));

				if (next[0] == 0)
					ans.push_back(next[2]);
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> now[0] >> now[1] >> now[2];

	BFS();
	sort(ans.begin(), ans.end());

	for (int i = 0; i < ans.size(); i++)
		cout << ans[i] << ' ';
}