백준 2251번 물통 C++

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

 

dfs방식을 이용해서 탐색하면서 A에 있는 물의 양이 0일 때 C에있는 물의 양을 저장해가면서 문제를 해결하였다.

탐색을 이미 했는지 확인하는 visited 은 A, B, C 중 2개만 검사하면 나머지는 값이 고정되기 때문에 visited 배열을 2차원 배열로 사용하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int visited[201][201] = { false };
int A, B, C;
set<int> ans;

void solve(int a, int b, int c) {
	visited[a][b] = true;
	if (a == 0) {
		ans.insert(c);
	}
	int spaceA = A - a;
	int spaceB = B - b;
	int spaceC = C - c;
	int nextA, nextB, nextC;
	if (a != 0) {
		//A->B
		if (spaceB >= a) {
			nextA = 0;
			nextB = b + a;
			nextC = c;
		}
		else {
			nextA = a - spaceB;
			nextB = B;
			nextC = c;
		}
		if (!visited[nextA][nextB]) solve(nextA, nextB, nextC);
		//A->C
		if (spaceC >= a) {
			nextA = 0;
			nextB = b;
			nextC = c + a;
		}
		else {
			nextA = a - spaceC;
			nextB = b;
			nextC = C;
		}
		if (!visited[nextA][nextB]) solve(nextA, nextB, nextC);
	}
	if (b != 0) {
		//B->A
		if (spaceA >= b) {
			nextA = a + b;
			nextB = 0;
			nextC = c;
		}
		else {
			nextA = A;
			nextB = b - spaceA;
			nextC = c;
		}
		if (!visited[nextA][nextB]) solve(nextA, nextB, nextC);
		//B->C
		if (spaceC >= b) {
			nextA = a;
			nextB = 0;
			nextC = b + c;
		}
		else {
			nextA = a;
			nextB = b - spaceC;
			nextC = C;
		}
		if (!visited[nextA][nextB]) solve(nextA, nextB, nextC);
	}
	if (c != 0) {
		//C->A
		if (spaceA >= c) {
			nextA = a + c;
			nextB = b;
			nextC = 0;
		}
		else {
			nextA = A;
			nextB = b;
			nextC = c - spaceA;
		}
		if (!visited[nextA][nextB]) solve(nextA, nextB, nextC);
		//C->B
		if (spaceB >= c) {
			nextA = a;
			nextB = b + c;
			nextC = 0;
		}
		else {
			nextA = a;
			nextB = B;
			nextC = c - spaceB;
		}
		if (!visited[nextA][nextB]) solve(nextA, nextB, nextC);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> A >> B >> C;
	solve(0, 0, C);

	for (auto a : ans) {
		cout << a << " ";
	}
};