C++ / 백준 / 2573 / 빙산

문제

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

2573번: 빙산

 

문제풀이

빙산의 높이를 입력받고 0이 아닌 높이를 입력받을 때 queue에 push 한다.

큐가 빌 때까지(큐가 비면 빙산이 모두 녹은 상태를 의미한다) 돌면서 1년이 지나면 따로 저장한 벡터를 빼어 남은 빙산의 상태를 갱신한다, 그리고 빙산 덩어리가 몇 덩어린지 확인을 하고 빙산 덩어리가 2개 이상이면 종료한다.

2개 이상이 아니면 인접한 부분 중 빙산이 없는 곳이 몇 개인지 세어 따로 벡터에 저장한다.

 

 

vector<vector<int>>iceberg;
vector<vector<int>>sub;
vector<vector<int>>near = { {-1,0},{1,0},{0,-1},{0,1} };
queue<pair<pair<int, int>, int>>q;
vector<vector<bool>>visit;

iceberg는 현재 빙산의 높이를 나타내는 벡터이다.

sub는 1년이 지났을 때 한 번에 계산하기 위한 뺄셈 벡터이다.

 

0 0 0 0 0 0 0
0 2 4 5 3 0 0
0 3 0 2 5 2 0

 

이처럼 있을 때 2의 경우는 1년이 지나면 인접한 부분이 0인 곳이 2곳이므로 사라진다.

4는 2가 사라져서 4-3이 아닌 4-2가 되어야 하므로 뺄셈을 한 번에 하는 것이 편해 보여서 따로 sub벡터를 만들었다.

큐 q는 {{ y좌표, x좌표}, 몇 년 지났는지}를 나타낸다.

visit은 방문 여부를 나타내는 벡터이다.

 

	int y = 0, x = 0;
	for (y = 0; y < N; ++y) {
		for (x = 0; x < M; ++x) {
			cin >> iceberg[y][x];
			if (iceberg[y][x] != 0)
				q.push({ { y,x },0 });
		}
	}

먼저 메인 문에서 입력을 받는 반복문이다.

입력받은 값을 iceberg벡터에 집어넣고, 그 값이 0이 아니라면 q에 집어넣는다.

 

int Melt() {
	int last_year = 0;
	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int year = q.front().second;
		q.pop();
		if (last_year == year - 1) {
			int mass_cnt = 0;
			Subtract();
			fill(visit.begin(), visit.end(), vector<bool>(M, false));
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < M; ++j) {
					if (iceberg[i][j] != 0 && !visit[i][j]) {
						Mass(i, j);
						mass_cnt++;
					}
				}
			}
			if (mass_cnt >= 2)
				return year;
		}
		for (int cnt = 0; cnt < 4; cnt++) {
			int n_y = y + near[cnt][0];
			int n_x = x + near[cnt][1];
			if (n_y >= 0 && n_y < N && n_x >= 0 && n_x < M) {
				if (iceberg[n_y][n_x] == 0)
					sub[y][x]++;
			}
		}
		if (iceberg[y][x] - sub[y][x] > 0) {
			q.push({ {y,x},year + 1 });
		}
		last_year = year;

	}
	return 0;
}

Melt함수는 BFS함수라고 보면 된다.

큐에는 빙산의 높이가 0이 아닌 좌표들만 저장되어있다.

y는 큐에 저장된 y값을, x는 x값을, year은 year값을 저장한다.

처음 Melt함수를 실행했을 때는 1년이 안 지났으므로, 윗부분의 if문은 넘어간다.

 

		for (int cnt = 0; cnt < 4; cnt++) {
			int n_y = y + near[cnt][0];
			int n_x = x + near[cnt][1];
			if (n_y >= 0 && n_y < N && n_x >= 0 && n_x < M) {
				if (iceberg[n_y][n_x] == 0)
					sub[y][x]++;
			}
		}

인접한 4곳이 0이라면 빼야 하므로 sub벡터에 1을 더한다.

 

		if (iceberg[y][x] - sub[y][x] > 0) {
			q.push({ {y,x},year + 1 });
		}
		last_year = year;

해당 좌표에서 인접한 부분의 상태를 모두 확인하였으면 그 수만 빼도 빙하의 높이가 1 이상이라면

큐에 y좌표, x좌표, 년수+1을 한다.

최근 연도를 year로 바꾼다.

맨 처음 메인 문에서 큐에 4개의 정보가 push 되었다면 4번을 pop 해야 벡터의 모든 범위를 1번 다 돌은 것이다.

 

		if (last_year == year - 1) {
			int mass_cnt = 0;
			Subtract();
			fill(visit.begin(), visit.end(), vector<bool>(M, false));
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < M; ++j) {
					if (iceberg[i][j] != 0 && !visit[i][j]) {
						Mass(i, j);
						mass_cnt++;
					}
				}
			}
			if (mass_cnt >= 2)
				return year;
		}

모든 범위를 한 번 돌았으면 last_year에는 이전 큐에서 불러온 year의 정보가 담겨있다.

따라서 if(last_year == year -1)은 벡터 한 바퀴 다 돌았을 때만 실행된다.

mass_cnt는 덩어리의 개수를 의미하는 변수이다.

Subtract함수는 iceberg벡터의 값 - sub벡터의 값을 하는 함수이다.

fill을 통해 visit벡터를 초기화한다.

visit벡터는 덩어리를 셀 때만 쓰기 때문에 덩어리를 세기 전에만 초기화하면 된다.

			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < M; ++j) {
					if (iceberg[i][j] != 0 && !visit[i][j]) {
						Mass(i, j);
						mass_cnt++;
					}
				}
			}

이 부분은 DFS함수라고 보면 된다.

덩어리가 mass_cnt에 저장되어있으므로 값이 2 이상이라면 year을 return 하면서 함수를 종료한다.

 

 

 

코드

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<vector<int>>iceberg;
vector<vector<int>>sub;
vector<vector<int>>near = { {-1,0},{1,0},{0,-1},{0,1} };
queue<pair<pair<int, int>, int>>q;
vector<vector<bool>>visit;

int N, M;

void Mass(int i, int j) {
	visit[i][j] = true;
	for (int cnt = 0; cnt < 4; ++cnt) {
		int n_i = i + near[cnt][0];
		int n_j = j + near[cnt][1];
		if (n_i >= 0 && n_i < N && n_j >= 0 && n_j < M) {
			if (iceberg[n_i][n_j] != 0 && !visit[n_i][n_j]) {
				Mass(n_i, n_j);
			}
		}
	}
}

void Subtract() {
	int y = 0, x = 0;
	for (y = 0; y < N; ++y) {
		for (x = 0; x < M; ++x) {
			iceberg[y][x] -= sub[y][x];
			if (iceberg[y][x] <= 0)
				iceberg[y][x] = 0;			
		}
	}
	fill(sub.begin(), sub.end(), vector<int>(M,0));
}

int Melt() {
	int last_year = 0;
	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int year = q.front().second;
		q.pop();
		if (last_year == year - 1) {
			int mass_cnt = 0;
			Subtract();
			fill(visit.begin(), visit.end(), vector<bool>(M, false));
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < M; ++j) {
					if (iceberg[i][j] != 0 && !visit[i][j]) {
						Mass(i, j);
						mass_cnt++;
					}
				}
			}
			if (mass_cnt >= 2)
				return year;
		}
		for (int cnt = 0; cnt < 4; cnt++) {
			int n_y = y + near[cnt][0];
			int n_x = x + near[cnt][1];
			if (n_y >= 0 && n_y < N && n_x >= 0 && n_x < M) {
				if (iceberg[n_y][n_x] == 0)
					sub[y][x]++;
			}
		}
		if (iceberg[y][x] - sub[y][x] > 0) {
			q.push({ {y,x},year + 1 });
		}
		last_year = year;

	}
	return 0;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M;

	iceberg = vector<vector<int>>(N, vector<int>(M, 0));
	sub = vector<vector<int>>(N, vector<int>(M, 0));
	visit = vector<vector<bool>>(N, vector<bool>(M, false));

	int y = 0, x = 0;
	for (y = 0; y < N; ++y) {
		for (x = 0; x < M; ++x) {
			cin >> iceberg[y][x];
			if (iceberg[y][x] != 0)
				q.push({ { y,x },0 });
		}
	}

	cout << Melt();

}