[C++] 백준(BOJ) - 14867 : 물통
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
용량이 다른 두 개의 빈 물통 A, B가 있다. 이 물통들에 물을 채우고 비우는 일을 반복하여 두 물통을 원하는 상태(목표하는 양의 물을 담은 상태)가 되도록 만들고자 한다. 물통 이외에는 물의 양을 정확히 잴 수 있는 방법이 없으며, 가능한 작업은 다음과 같은 세 종류가 전부이다.
예를 들어, 물통 A와 B의 용량이 각각 2리터와 5리터라고 하자. 두 물통 모두 빈 상태에서 시작하여 최종적으로 물통 A에는 2리터, 물통 B에는 4리터 물을 남기길 원할 경우, 다음과 같은 순서로 작업을 수행하면 총 8회의 작업으로 원하는 상태에 도달할 수 있다.
(0,0)→[F(B)]→(0,5)→[M(B,A)]→(2,3)→[E(A)]→(0,3)→[M(B,A)]→(2,1)→[E(A)]→(0,1)→[M(B,A)]→(1,0)→[F(B)]→(1,5)→[M(B,A)]→(2,4)
하지만, 작업 순서를 아래와 같이 한다면 필요한 작업 총 수가 5회가 된다.
(0,0)→[F(A)]→(2,0)→[M(A,B)]→(0,2)→[F(A)]→(2,2)→[M(A,B)]→(0,4)→[F(A)]→(2,4)
두 물통의 용량과 원하는 최종 상태를 입력으로 받은 후, 두 물통이 비어 있는 상태에서 시작하여 최종 상태에 도달하기 위한 최소 작업 수를 구하는 프로그램을 작성하시오.
입력
표준 입력으로 물통 A의 용량을 나타내는 정수 a(1 ≤ a < 100,000), 물통 B의 용량을 나타내는 정수 b(a < b ≤ 100,000), 최종 상태에서 물통 A에 남겨야 하는 물의 용량을 나타내는 정수 c(0 ≤ c ≤ a), 최종 상태에서 물통 B에 남겨야 하는 물의 용량을 나타내는 정수 d(0 ≤ d ≤ b)가 공백으로 분리되어 한 줄에 주어진다.
출력
목표 상태에 도달하는 최소 작업 수를 나타내는 정수를 표준 출력으로 출력한다. 만약 목표 상태에 도달하는 방법이 없다면 –1을 출력한다.
서브태스크
| 번호 | 배점 | 제한 | |
| 1 | 9 | A 물통의 용량은 1리터 | |
| 2 | 14 | B 물통의 용량은 A 물통의 용량의 배수 | |
| 3 | 34 | 1 ≤ a, b ≤ 1,000 | |
| 4 | 43 | 원래의 제약조건 이외에 아무 제약조건이 없다. |
알고리즘
- BFS
- 맵
풀이
- 최소 작업수 구하기
- 가중치가 같은 DAG 그래프의 최소값 구하기 BFS
- 상태값 2개 (a, b)
- 작업의 경우의 수는 총 6개 (F(a), F(b), E(a), E(b), M(a,b), M(b,a))
- a, b의 각 최대용량은 10만
- 10만 * 10만 배열은 너무 크다
- 연속적인 상태값(dense)을 쓰지 않는다 => sparse한 상태값은
map 자료구조활용
- move(a,b) 함수를 max와 min을 이용하여 한줄 코딩!
코드
// BOJ - 14867 : 물통
#include<bits/stdc++.h>
using namespace std;
const int INF = 2147000000;
int a, b, c, d;
map<pair<int,int>, int> mp;
queue<pair<int, int>> q;
void enqueue(int x, int y, int d)
{
if (mp[{x, y}]) return;
mp[{x, y}] = d + 1;
q.push({ x,y });
}
int bfs(int x, int y)
{
// x와 y는 a와 b에 각각 남아있는 물의 양
mp[{x, y}] = 1; // visited[y][x] = 1 과 동일 (초기 방문처리)
q.push({ x,y });
while (!q.empty())
{
x = q.front().first;
y = q.front().second;
q.pop();
// 6가지 경우의 수 함수로 처리
enqueue(a, y, mp[{x, y}]); // A 채우기
enqueue(x, b, mp[{x, y}]); // B 채우기
enqueue(0, y, mp[{x, y}]); // A 비우기
enqueue(x, 0, mp[{x, y}]); // B 비우기
enqueue(max(0, x + y - b), min(x + y, b), mp[{x, y}]); // A -> B
enqueue(min(x + y, a), max(0, x + y - a), mp[{x, y}]); // B -> A
}
if (mp[{c, d}]) return mp[{c, d}] - 1;
else return -1;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> a >> b >> c >> d;
cout << bfs(0, 0);
return 0;
}
평가
- 가중치가 같은 DAG 그래프의 최소값 구하기 (BFS)
