백준 2573 _ 빙산

www.acmicpc.net/problem/2573

2573번: 빙산

---

✨ 내 소스 코드

#include<iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <string.h>

int route[4][2] = { {-1,0},{0,-1},{0,1},{1,0} };
bool visit[301][301];
using namespace std;
int v[301][301];
int N, M;

void DFS(int init_x, int init_y) {
	visit[init_x][init_y] = true;

	for (int i = 0; i < 4; i++) {
		int nx = init_x + route[i][0];
		int ny = init_y + route[i][1];

		if (nx < 1 || nx >= N - 1 || ny < 1 || ny >= M - 1) continue;
		if (v[nx][ny] > 0 && !visit[nx][ny]) DFS(nx, ny);
	}
}

void year() {
	int vec[301][301];
	for (int x = 0; x < N; x++)
		for (int y = 0; y < M; y++)
			vec[x][y] = v[x][y];
	for (int i = 1; i < N - 1; i++) {
		for (int j = 1; j < M - 1; j++) {
			if (vec[i][j] != 0) {
				int temp = 0;
				for (int z = 0;z < 4;z++) {
					if (vec[i + route[z][0]][j + route[z][1]] == 0) {
						temp++;
					}
				}
				if (v[i][j] - temp < 0) {
					v[i][j] = 0;
				}
				else {
					v[i][j] = v[i][j] - temp;
				}
			}
			
		}
	}
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	vector<int> t;
	int result = 0;
	cin >> N >> M;
	

	for (int i = 0; i < N;i++) {
		for (int j = 0;j < M;j++) {
			cin >> v[i][j];
		}
	}

	while (1) {
		int island_count=0;
		memset(visit, false, sizeof(visit));
		bool check=false;
		for (int i = 1; i < N - 1; i++) {
			for (int j = 1; j < M - 1; j++) {
				if (v[i][j] > 0 && !visit[i][j]) {
					island_count++;
					if (island_count >= 2) {
						check = true;
						break;
					}
					DFS(i, j);
				}
			}
		}
		if (check) break;
		if (island_count == 0) {
			cout << "0";
			return 0;
		}
		year();
		result++;
		
	}
	cout << result;

	return 0;
}

 

🙏 문제 풀이

DFS로 탐색 -> 덩어리가 몇개인지 찾기

 

year() -> 1년이 지났을때의 빙산 모습으로 바꾸기

이때, 인접한 0의 개수를 세는 것은 아래의 경우때문에 빙산의 복사본으로 하여야 된다

4는 원래 근접한 0이 1개 밖에 없어서 3이 되어야 되나, 이전에 0이 되어버린 2때문에 4가 3이 아니라 2가 되어버리는 일이 일어난다

 

⭐ 문제 풀이 결과