백준 Baekjoon 2573 빙산 풀이

사용언어

Visual studio 2019 C++

문제 간단요약

빙산에 4면중 0(물)이 닿은 수만큼 빼서 두개나 그 이상으로 나눠질때 까지 빼기

생각하기

N년후 빙산구하기 dfs로 몇개로 나눠져있는지 구하기 만약 0개이면 0출력!

[2573 풀이]

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int N, M;
int bing[300][300];
int bing2[300][300];
 // 두개로 하는이유는 하나로 했을경우 0,0이 변하면 주변(0,1)과 (1,0)도 달라지기 때문에
int gogoA[4] = { 0,1,0,-1 };
int gogoB[4] = { 1,0,-1,0 };
vector<pair<int, int>> v;
bool visited[300][300];

void kind(int a, int b) {
	if (visited[a][b])
		return;
	visited[a][b] = true;

	for (int i = 0; i < 4; i++) {
		int A = a + gogoA[i];
		int B = b + gogoB[i];

		if (A >= 0 && A < N && B >= 0 && B < M) {
			if (!visited[A][B] && bing[A][B])
				kind(A, B);
		}
	}
}

int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> bing[i][j];
			if (bing[i][j] != 0)
				v.push_back(make_pair(i, j));
		}
	}
	int n = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++)
			bing2[i][j] = bing[i][j];
	}
	int year = 0;
	int d = 0;
	bool b = false;
	while (1) {
		for (int i = 0; i < v.size(); i++) {
			pair<int, int> p = v[i];
			int cnt = 0;
			for (int j = 0; j < 4; j++) {
				int A = p.first + gogoA[j];
				int B = p.second + gogoB[j];

				if (A >= 0 && A < N && B >= 0 && B < M) {
					if (bing[A][B] == 0)
						cnt++; // 빙산주변의 바다의 면
				}
			}
			bing2[p.first][p.second] -= cnt;
			if (bing2[p.first][p.second] < 0)
				bing2[p.first][p.second] = 0;
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++)
				bing[i][j] = bing2[i][j];
		}

		memset(visited, false, sizeof(visited)); // 1년 지날때마다 다시 해야되니 초기화
		d = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (bing[i][j] != 0 && !visited[i][j]) {
					kind(i, j);
					d++; // 빙산이 나눠진 개수
				}
			}
		}
		year++; // +1년
		if (d > 1)
			break; // 빙산이 나눠지면 멈춤
		if (d == 0) { 
			b = true;
			break;
		} // 빙산이 안생기고 0이될 경우 break
	}
	if (b) // 만약 녹아서 빙산이 안나눠지고 녹는다면
		cout << 0 << "\n";
	else
		cout << year << "\n";
}