[BOJ/Gold 1] 백준 22956 소나기(C++)

문제 링크

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

22956번: 소나기

 

문제

신촌에는 N×M 크기의 신촌평야가 있다. 이 신촌평야에 Q일간 소나기가 온다고 한다. 신촌평야의 좌측 상단의 좌표는 (1, 1)이며, 우측 하단의 좌표는 (N, M)이다.

소나기는 (a, b) 칸에 내리며, 내린 후에는 땅의 높이가 c만큼 감소하며 해당 칸에 물이 남는다. 땅의 높이는 음수가 될 수 있다.

만약 인접한 칸에 물이 있다면 각 칸의 물이 연결된다. 각 칸이 한 개의 변을 공유하고 있으면 두 칸이 인접한다고 한다.

신촌평야 관리본부에서는 수질검사를 위해 소나기가 내린 후 그 지점에 수질 검사 로봇을 설치한다. 이 로봇은 연결된 물로 자유롭게 이동하다가 높이가 가장 낮은 칸에서 검사를 마친다. 만약 높이가 가장 낮은 칸이 여러 개 있다면, 비가 내린 지 가장 오래된 칸에서 검사를 마친다. 

총 Q일간 소나기가 내릴 곳이 주어질 때, 각 날짜마다 로봇이 검사를 마치는 지점을 출력하는 프로그램을 만들어 보자.

입력

첫 번째 줄에 공백을 기준으로 N(1≤N≤1000),  M(1≤M≤1000), Q(1≤Q≤100000)가 정수로 주어진다.

두 번째 줄부터 N+1번째 줄까지 신촌평야의 각 칸의 높이 정보 H(0≤Ha,b≤1000)가 정수로 주어진다.

 N+2번째 줄부터 N+Q+1번째 줄까지 순서대로 비가 올 칸의 좌표인 a(1≤a≤N), b(1≤b≤M), 땅의 높이가 감소되는 정도인 c(1≤c≤100) 가 정수로 주어진다.

출력

각 날짜마다 로봇이 검사를 마치는 지점의 좌표를 한 줄씩 차례대로 출력한다.

예제 입력 1

2 3 5
9 9 9
9 9 9
1 1 1
1 2 2
2 2 2
1 1 5
1 2 1

예제 출력 1

1 1
1 2
1 2
1 1
1 1

예제 입력 2

4 5 14
0 9 9 9 9
9 9 0 0 0
0 9 0 0 0
0 9 9 9 0
1 4 1
1 3 1
1 2 1
1 5 2
4 3 1
4 2 1
3 2 1
4 4 2
2 1 2
2 2 1
2 2 1
1 2 1
1 2 1
1 5 1

예제 출력 2

1 4
1 4
1 4
1 5
4 3
4 3
4 3
4 4
2 1
1 5
1 5
1 5
1 2
1 2

힌트

다음은 예제 1번의 그림이다.

알고리즘 분류

• 유니온 파인드

풀이

다음과 같은 과정을 Q번 반복한다.

(A, B) 칸의 높이를 C만큼 줄이고 비가 내린 시간을 기록한다. 그리고 상하좌우 4방향과 비교해서 물이 있다면, 같은 그룹이 아니라면 유니온 파인드를 사용하여 같은 그룹으로 묶고, 같은 그룹이라면 현재 그룹의 Parent의 높이 및 비가 내린 시간을 비교해서 높이가 현재 칸이 더 낮다면 Parent를 현재 칸으로 바꾸고, 높이가 같은데 현재 칸이 비가 내린 지 더 오래 된 칸이라면 마찬가지로 Parent를 현재 칸으로 바꾼다. 즉, 어떤 그룹의 Parent는 높이가 가장 낮고, 높이가 같은 칸들 중에서 비가 내린 지 가장 오래 된 칸을 의미한다.

로봇은 반드시 높이가 가장 낮고, 높이가 같은 칸들 중에서 비가 내린 지 가장 오래 된 칸에 존재해야 하므로, 현재 칸이 소속되어 있는 그룹의 Parent를 출력한다.

이 Parent를 기록하지 않고 일일히 로봇이 존재해야 하는 칸을 찾는다면 시간 제한을 넘어가버리기 때문에, Parent를 어떻게 기록해야 하는 지를 파악하는 것이 중요한 문제였다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1001
#define LL long long
#define INF 1e9

using namespace std;
int N, M, Q;
int H[MAX][MAX];
int Water[MAX][MAX];
pair<int, int> Parent[MAX][MAX];
int moveY[4] = { -1,0,1,0 };
int moveX[4] = { 0,-1,0,1 };
bool visited[MAX][MAX];

void Init() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			Parent[i][j] = make_pair(i, j);
		}
	}
}

pair<int, int> Find(pair<int, int> A) {
	if (Parent[A.first][A.second] == make_pair(A.first, A.second)) {
		return make_pair(A.first, A.second);
	}
	return Parent[A.first][A.second] = Find(Parent[A.first][A.second]);
}

void Union(pair<int, int> A, pair<int, int> B) {
	pair<int, int> PA = Find(A);
	pair<int, int> PB = Find(B);
	int PAY = PA.first;
	int PAX = PA.second;
	int PBY = PB.first;
	int PBX = PB.second;
	if (H[PAY][PAX] < H[PBY][PBX]) {
		Parent[PB.first][PB.second] = PA;
	}
	else if (H[PAY][PAX] > H[PBY][PBX]) {
		Parent[PA.first][PA.second] = PB;
	}
	else {
		if (Water[PAY][PAX] < Water[PBY][PBX]) {
			Parent[PB.first][PB.second] = PA;
		}
		else if (Water[PAY][PAX] > Water[PBY][PBX]) {
			Parent[PA.first][PA.second] = PB;
		}
	}
}

void Input() {
	cin >> N >> M >> Q;
	Init();
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			cin >> H[i][j];
		}
	}
}

void Find_Answer() {
	for (int i = 1; i <= Q; i++) {
		int A, B, C;
		cin >> A >> B >> C;
		H[A][B] -= C;
		Water[A][B] = i;
		for (int j = 0; j < 4; j++) {
			int nextY = A + moveY[j];
			int nextX = B + moveX[j];
			if ((nextY >= 1) && (nextY <= N) && (nextX >= 1) && (nextX <= M) && (Water[nextY][nextX] != 0)) {
				if (Find(make_pair(A, B)) != Find(make_pair(nextY, nextX))) {
					Union(make_pair(A, B), make_pair(nextY, nextX));
				}
				else {
					pair<int, int> nextP = Find(make_pair(nextY, nextX));
					if (H[A][B] < H[nextP.first][nextP.second]) {
						Parent[A][B] = make_pair(A, B);
						Union(make_pair(A, B), make_pair(nextY, nextX));
					}
					else if (H[A][B] == H[nextP.first][nextP.second]) {
						if (Water[A][B] < Water[nextP.first][nextP.second]) {
							Parent[A][B] = make_pair(A, B);
							Union(make_pair(A, B), make_pair(nextY, nextX));
						}
					}
				}
			}
		}
		pair<int, int> answer = Find(make_pair(A, B));
		cout << answer.first << " " << answer.second << "\n";
	};
}

int main() {
	FASTIO
	Input();
	Find_Answer();

	return 0;
}