글 읽기 - 왜 맞을까요...

sochun1518 3년 전 1

visited 배열을 2차원으로 선언하면 [100000][100000] 으로 선언이 불가능해서 Map으로 선언한다음에 단순 BFS 탐색으로 구현했습니다.

그러면, 최대 경우의 수가 10^5 * 10^5 가 최대 생길텐데 왜 시간초과도 안나고, Map에도 최대 10^5 * 10^5 개의 값이 들어갈텐데 메모리 초과도 안날까요...?? 도저히 visited 를 선언할 방법이 안보여서 Map으로 때려봤는데 맞았네요...?

#include<iostream>
#include<map>
#include<queue>

using namespace std;

int a, b, A, B;
map<pair<int, int>, int> visited;
queue<pair<pair<int, int>, int>> q;

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

	cin >> a >> b >> A >> B;

	q.push({ {0, 0}, 0 });
	visited.insert({ {0, 0}, 0 });
	while (!q.empty()) {
		pair<int, int> cur = q.front().first;
		int curL = q.front().second;
		q.pop();

		if (visited[{cur.first, cur.second}] < curL) continue;
		if (cur.first == A && cur.second == B) break;

		// Fill(A)
		if (cur.first < a) {
			if (visited.find({ a, cur.second }) == visited.end() ||
				curL + 1 < visited[{a, cur.second}]) {
				visited.insert({ {a, cur.second}, curL + 1 });
				q.push({ {a, cur.second}, curL + 1 });
			}
		}
		// Fill(B)
		if (cur.second < b) {
			if (visited.find({ cur.first, b }) == visited.end() ||
				curL + 1 < visited[{cur.first, b}]) {
				visited.insert({ {cur.first, b}, curL + 1 });
				q.push({ {cur.first, b}, curL + 1 });
			}
		}
		// Empty(A)
		if (0 < cur.first) {
			if (visited.find({ 0, cur.second }) == visited.end() ||
				curL + 1 < visited[{0, cur.second}]) {
				visited.insert({ {0, cur.second}, curL + 1 });
				q.push({ {0, cur.second}, curL + 1 });
			}
		}
		// Empty(B)
		if (0 < cur.second) {
			if (visited.find({ cur.first, 0 }) == visited.end() ||
				curL + 1 < visited[{cur.first, 0}]) {
				visited.insert({ {cur.first, 0}, curL + 1 });
				q.push({ {cur.first, 0}, curL + 1 });
			}
		}
		int newA, newB, diff;
		// Move A to B
		// A물통이 줄 수 있는 양과 B물통이 받을 수 있는 양 중 작은 값이 이동 가능!
		diff = min(b - cur.second, cur.first);
		newA = cur.first - diff;
		newB = cur.second + diff;
		if (visited.find({ newA, newB }) == visited.end() ||
			curL + 1 < visited[{newA, newB}]) {
			visited.insert({ {newA, newB}, curL + 1 });
			q.push({ { newA, newB}, curL + 1 });
		}
		// Move B to A
		diff = min(a - cur.first, cur.second);
		newA = cur.first + diff;
		newB = cur.second -  diff;
		if (visited.find({ newA, newB }) == visited.end() ||
			curL + 1 < visited[{newA, newB}]) {
			visited.insert({ {newA, newB}, curL + 1 });
			q.push({ { newA, newB}, curL + 1 });
		}
	}
	visited.find({ A, B }) == visited.end() ? (cout << -1 << '\n') : (cout << visited[{A, B}] << '\n');

	return 0;
}

jjang36524 3년 전 1

실제 가능한 경우의 수는 이보다 적습니다. 잘 생각해보세요.

jinsoolve 2년 전 2

주의!!!!

아직 공부하는 도중이므로 틀린 논리일수도 있습니다. 혹시 제 말에 틀린 부분이 있다면 가감없이 공격 부탁드립니다.

----------------------------------------------------------------------------

저도 같은 의문을 갖고 있었는데,

(A 물통에 든 물의 양, B 물통에 든 물의 양)이라 할 때 worst case(a = 99,999, b = 100,000)가

(0 ~ 99999, 0), (0 ~ 99999, 100000), (0, 0 ~ 100000), (9999, 0 ~ 100000) 이 되어서

대강 4 * 100,000 의 케이스만 존재하기 때문에 그런 것이라 생각합니다.

최소한 한 쪽이 [비어 있거나], [꽉 차 있는] 이유는 작업의 경우를 생각하면 됩니다.

1. Fill의 경우, 당연히 최소 둘 중 하나는 꽉 차 있겠죠.

2. Empty의 경우, 당연히 최소 둘 중 하나는 비어 있겠죠.

3. Move의 경우,

A->B이면, 다 옮길 수 있어서 A가 0이 되거나, 다 옮기기 전에 B가 꽉 차거나 이고

B->A이면, 다 옮길 수 있어서 B가 0이 되거나, 다 옮기기 전에 A가 꽉 차거나 이다.

따라서, 저는 위에서 말한 전제가 참이라고 생각했습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

왜 맞을까요...

sochun1518 3년 전 1

jjang36524 3년 전 1

jinsoolve 2년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말