Beakjoon] 물통 (백준 2251코테) - 그래프 (C++)

---

🅰️문제주소 : https://www.acmicpc.net/problem/2251

 

🚩문제 

 

 

🪡풀이 

 - 그래프로 map을 그려놓고 BFS, DFS 하는 것이 아닌 역으로 그래프를 그리는 문제
 - 2차원 길찾기와 유사하게 물의 이동의 케이스를 배열로 구성한다. (0->1, 0->2, 1->0, 1->2, 2->0, 2->1)
 - 방문여부는 A와 B의 물통 양으로 이차원 배열을 만들어서 체크한다.
 - A, B, C의 물통의 양을 입력받은 뒤 BFS탐색을 시작하되 이동할 노드를 큐에 추가하고(예:0에서 1)
방문한 경우는 제외시킨다.
 - 받는물통한테 보내는 물통의 모든 용량을 추가한 뒤 기존 물통의 크기를 초과한 경우 초과한 만큼 다시 보내는 물통으로 보낸다. 초과하지 않았을 경우 보내는 물통은 0을 저장한다.
 - 이 과정 후 A의 물통이 0이면 C물통의 용량을 정답 배열에 true로 변경한다

 

 

☕코드는 아래 숨김

#include <iostream>
#include <vector>
#include <queue>

bool answer[201];
int now[3];
int sender[] = { 0, 0, 1, 1, 2, 2 };
int reciver[] = { 1, 2, 0, 2, 0, 1 };
bool visited[201][201];


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

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

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

			if (next[reciver[i]] > now[reciver[i]]) {
				next[sender[i]] = next[reciver[i]] - now[reciver[i]];
				next[reciver[i]] = now[reciver[i]];
			}
			if (!visited[next[0]][next[1]]) {
				visited[next[0]][next[1]] = true;
				q.push(std::make_pair(next[0], next[1]));
				if (next[0] == 0) {
					answer[next[2]] = true;
				}
			}
		}
	}
}

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

	std::cin >> now[0] >> now[1] >> now[2];
	BFS();

	for (int i = 0; i < 201; ++i) {
		if (answer[i])
			std::cout << i << " ";
	}

	
	return 0;
}

 

💡알게 된 것 

 - 제법 어려웠던 문제. 수도코드를 보고도 감을 잡기 어려웠다.
 - 이차원 지도에서 빠른 길 찾기 같은 것을 풀 때 쓰던 좌표값 같은 것을 물의 이동으로 그려서 표현하는 것
 - 어렵다 어려워

 

---