백준 14867 - 물통(C++)

문제 링크입니다. https://www.acmicpc.net/problem/14867

14867번: 물통

BFS와 map을 이용한 문제였습니다.

문제 조건

출력 예시

이차원 배열을 선언하기에는 100,000 * 100,000 크기이기에 메모리 초과가 됩니다.

따라서 map을 이용하여, 도착했는지의 유무를 확인했습니다.

 

먼저 F(X)와 E(X)의 경우는 문제 조건 그대로 탐색해주면 됩니다.

M(X,Y)의 경우에는 X -> Y로 Y -> X로 가는 2가지 경우가 있는데,

 

1. X -> Y의 경우

X의 남은 양이 Y에 남아있는 빈 공간보다 큰 경우와 작은 경우가 있습니다.

Y에 남아있는 빈 공간보다 큰 경우는 X의 값은 0이 되고, Y의 값은 X + Y가 됩니다.

Y에 남아있는 빈 공간보다 작은 경우는 X의 값은 X - B + Y이 되고, Y의 값은 B가 됩니다.

 

2. Y -> X의 경우

1번의 경우와 동일하게 하면 됩니다.

 

문제 접근 방법

1. (0 , 0)에서 시작해서 F(X), E(X), M(X,Y)의 경우를 모두 확인합니다.

2. (C, D)에 도달하면 Cnt의 값을 출력합니다.

3. 도달하지 못했다면 -1을 return 합니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <map>

using namespace std;

int a, b, c, d;
map<pair<int, int>, int> check;


int bfs() {
	queue<pair<int, int>> q;
	q.push(make_pair(0, 0));
	check[make_pair(0, 0)] = 0;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		int cnt = check[make_pair(x, y)];
		//cout << x << " " << y << " " << cnt << "\n";
		q.pop();
		if (x == c && y == d) {
			return cnt;
		}
		//F(x)
		if (check[make_pair(a, y)] == 0) {
			check[make_pair(a, y)] = cnt + 1;
			q.push(make_pair(a, y));
		}
		if (check[make_pair(x, b)] == 0) {
			check[make_pair(x, b)] = cnt + 1;
			q.push(make_pair(x, b));
		}
		//E(x)
		if (check[make_pair(x, 0)] == 0) {
			check[make_pair(x, 0)] = cnt + 1;
			q.push(make_pair(x, 0));
		}
		if (check[make_pair(0, y)] == 0) {
			check[make_pair(0, y)] = cnt + 1;
			q.push(make_pair(0, y));
		}
		//M(x,y)
		int xx, yy;
		if (x <= b - y) {
			xx = 0;
			yy = y + x;
			if (check[make_pair(xx, yy)] == 0) {
				check[make_pair(xx, yy)] = cnt + 1;
				q.push(make_pair(xx, yy));
			}
		}
		else{
			xx = x - b + y;
			yy = b;
			if (check[make_pair(xx, yy)] == 0) {
				check[make_pair(xx, yy)] = cnt + 1;
				q.push(make_pair(xx, yy));
			}
		}
		if (y <= a - x) {
			yy = 0;
			xx = x + y;
			if (check[make_pair(xx, yy)] == 0) {
				check[make_pair(xx, yy)] = cnt + 1;
				q.push(make_pair(xx, yy));
			}
		}
		else {
			yy = y - a + x;
			xx = a;
			if (check[make_pair(xx, yy)] == 0) {
				check[make_pair(xx, yy)] = cnt + 1;
				q.push(make_pair(xx, yy));
			}
		}
	}
	return -1;
}

void solve() {
	int ans = bfs();
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> a >> b >> c >> d;
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!