백준 2276: 물 채우기

https://www.acmicpc.net/problem/2276

 

유사한 문제

이 문제를 보자마자 떠올린 문제가 있다.

https://www.acmicpc.net/problem/1113

 

바로, "백준 1113: 수영장 만들기"이다. 이 문제는 바깥에서부터 물의 수위를 조절하며, BFS를 돌아서, 채울 수 있는 물을 구하면 된다.

 

다만, 이 문제는 물의 수위가 1~10 사이여서 가능하였고, 여기서 다룰 문제는 1~1,000,000,000까지의 높이를 가지므로 다른 해결책을 강구해야한다.

 

시도한 아이디어

그래서 나는 물통의 높이들을 전부 우선순위 큐에 넣고, 높이가 작은 순서대로 순회하는 알고리즘을 떠올렸다.

일단 우선순위 큐에서 높이와 위치를 꺼낸 뒤에, 위치를 기준으로 DFS를 돌며, 주위의 높이 중 가장 작은 높이를 구한다. 만약, 현재 높이와 같은 높이가 있다면 그 위치로 옮기고, 주위 높이를 구한다. 만약 주위 중 하나가 바깥이면, 음수를 리턴한다.

 

DFS를 돈 뒤에, 리턴된 값이 음수라면 아무것도 안하고 아니라면, 지금까지 DFS를 돈 곳의 높이를 리턴값으로 바꿔서, 이전 값과의 이를 정답에 더한다. 이런 방식이였다.

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

priority_queue<pair<int, pair<int, int>>> pq;
int H[302][302], N, M, ans = 0;
bool v[302][302];
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
bool inRange(int y, int x)
{
	return y > 0 && x > 0 && y <= N && x <= M;
}
int dfs(vector<pair<int, int>> &r, int y, int x)
{
	r.push_back({ y, x });
	v[y][x] = true;
	int ret = 1000000007;
	for (int d = 0; d < 4; d++)
	{
		int ny = y + dy[d];
		int nx = x + dx[d];
		if (!inRange(ny, nx)) return -1;
		if (v[ny][nx]) continue;
		if (H[y][x] == H[ny][nx])
			ret = min(ret, dfs(r, ny, nx));
		else
			ret = min(ret, H[ny][nx]);
	}
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> M >> N;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
		{
			cin >> H[i][j];
			pq.push({ -H[i][j], {i, j} });
		}
	while(!pq.empty())
	{
		int h = -pq.top().first;
		int y = pq.top().second.first;
		int x = pq.top().second.second;
		pq.pop();
		if (h != H[y][x]) continue;
		vector<pair<int, int>> route;
		memset(v, false, sizeof(v));
		int a = dfs(route, y, x);
		if (a > 0)
		{
			for (int i = 0; i < route.size(); i++)
			{
				const int& y = route[i].first;
				const int& x = route[i].second;
				ans += (a - H[y][x]);
				H[y][x] = a;
			}
			pq.push({ -a, {y, x} });
		}
		else
			H[y][x] = -1;
	}
	cout << ans << '\n';
}

예제는 맞고, 만들어본 테스트 케이스들도 괜찮아서, 제출 시도는 해보았지만, 역시나 우려했던 대로 "시간 초과"다. v를 매번 초기화하는 memset이나, 중복해서 순회하는 DFS가 눈에 거슬린다. 혹시 몰라서, 모든 높이가 아닌, 같은 높이를 가진 클러스터 하나만 넣도록 시도는 했지만.

void dfs2(int y, int x)
{
	v[y][x] = true;
	for (int d = 0; d < 4; d++)
	{
		int ny = y + dy[d];
		int nx = x + dx[d];
		if (!inRange(ny, nx) || v[ny][nx] || H[ny][nx] != H[y][x]) continue;
		dfs2(ny, nx);
	}
}
for(int i = 1; i <= N; i++)
	for(int j = 1; j <= M; j++)
		if (!v[i][j])
		{
			dfs2(i, j);
			pq.push({ -H[i][j], {i, j} });
		}

 

역시나 이것도 "시간 초과"다.

 

처음으로.

결국 나는 구글링을 거쳤다.

https://codersbrunch.blogspot.com/2016/12/2276.html

2276번: 물 채우기

코드를 읽은 결과, 처음에 내가 언급한 아이디어와 유사했다. 처음 문제의 아이디어가 1~10까지의 수위를 조정해서 문제를 해결하는 것이라면, 이 문제의 아이디어는 주위의 높이 사이에서, 문제를 해결한다.

또한, 우선 순위 큐를 사용해서, 작은 높이 부터 순회하면, 문제를 빠르게 해결할 수 있다.

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

priority_queue<pair<int, pair<int, int>>> pq;
int H[302][302], N, M, ans = 0;
bool v[302][302];
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, -1, 1 };
bool inRange(int y, int x)
{
	return y > 0 && x > 0 && y <= N && x <= M;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> M >> N;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= M; j++)
		{
			cin >> H[i][j];
			if (i == 1 || j == 1 || j == M || i == N)
			{
				v[i][j] = true;
				pq.push({ -H[i][j], {i, j} });
			}
		}
	while(!pq.empty())
	{
		int h = -pq.top().first;
		int y = pq.top().second.first;
		int x = pq.top().second.second;
		pq.pop();
		for(int d = 0; d < 4; d ++)
		{
			int ny = y + dy[d];
			int nx = x + dx[d];
			if (!inRange(ny, nx) || v[ny][nx]) continue;
			v[ny][nx] = true;
			if (H[ny][nx] > h) pq.push({ {-H[ny][nx]}, {ny, nx} });
			else
			{
				ans += h - H[ny][nx];
				pq.push({ -h, {ny, nx} });
			}
		}
	}
	cout << ans << '\n';
}

 

이전 코드를 좀 더 연구했다면, 해결했을 문제였다. 새로운 것을 하려하다 보니, 너무 시간을 낭비한 것 같다.