[백준 알고리즘] 빙산.txt

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef struct loc {
	int r, c;
	int minor;
}Loc;


int dr[4] = {-1,0,1,0};
int dc[4] = { 0,1,0,-1 };

int result;
int whole;
int n, m;
int arr[303][303];
bool visit[303][303];

vector <Loc> root;
queue <Loc> visitCheck;

void dfs(Loc temp) {
	for (int dir = 0; dir < 4; dir++) {
		int r = temp.r + dr[dir];
		int c = temp.c + dc[dir];
		if (r >= 0 && r < n && c >= 0 && c < m && arr[r][c] != 0 && visit[r][c] == false) {
			whole+=1;
			visit[r][c] = true;
			dfs({ r,c });
		}
	}
}
int main() {
	result = 0;
	scanf("%d %d", &n, &m);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &arr[i][j]);
			if (arr[i][j] != 0) {
				root.push_back({ i,j });
			}
		}
	}

	for (int time = 1; ; time++) {
		//printf("%d\n", time);

		for (int i = 0; i < root.size(); i++) {	//순차접근시의 문제
			int count = 0;
			for (int dir = 0; dir < 4; dir++) {
				if (arr[root[i].r + dr[dir]][root[i].c + dc[dir]] == 0) {
					count++;
				}
			}
			root[i].minor = count;
		}

		for (int i = 0; i < root.size(); i++) {	//순차접근시의 문제
			arr[root[i].r][root[i].c] -=root[i].minor;
			if (arr[root[i].r][root[i].c] <= 0) {
				arr[root[i].r][root[i].c] = 0;
				root.erase(root.begin() + i);
				i--;
			}
		}

		

		if (root.empty()) {break;}
		if (!root.empty()) {
			whole++;
			visit[root[0].r][root[0].c] = true;
			dfs(root[0]);
		}

		//printf("whole:%d rootsize:%d\n", whole, root.size());
		if (whole != root.size()) {
			result = time;
			break;
		}
		whole = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				visit[i][j] = false;
			}
		}
	}

	printf("%d", result);
	return 0;
}