Algorithm_bj_DFS-BFS/BJ_2573_빙산.cpp at master · heewonham/Algorithm_bj_DFS-BFS · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#include <iostream>
#include <queue>
using namespace std;
queue <pair<pair<int, int>, int>> melt1;
queue <pair<pair<int, int>, int>> melt2;
int ice[300][300];
int visited[300][300];

int BFS(int cc, int N, int M, int X, int Y);
int pole(int x, int y, int N, int M);
int main() {
	int i, j, count = 0, year = 0;
	int N, M, x, y;

	// 1. 입력
	cin >> N >> M;
	for (i = 0; i < N; i++) {
		for (j = 0; j < M; j++) {
			cin >> ice[i][j];
			if (ice[i][j] > 0) { count++;	x = i; y = j; }
			visited[i][j] = 1;
	}	}

	// 2. 찾기
	year = BFS(count, N, M,x,y);

	// 3. 출력
	cout << year;
}
int BFS(int cc, int N, int M, int X, int Y) {
	int status, x, y, c;
	int count = cc;
	int year = 0, xx = X, yy = Y;
	while (count > 0) {
		// # 넣는다.
		status = 1;
		melt1.push(make_pair(make_pair(xx, yy), 0));
		melt2.push(make_pair(make_pair(xx, yy), 0));
		visited[xx][yy] *= -1;
		while (!melt1.empty()) {
			x = melt1.front().first.first;
			y = melt1.front().first.second;
			melt1.pop();
			if (x - 1 >= 0 && visited[x - 1][y] == 1 && ice[x - 1][y] != 0) {
				melt1.push(make_pair(make_pair(x - 1, y), 0));
				melt2.push(make_pair(make_pair(x - 1, y), 0));
				visited[x - 1][y] *= -1; status++;
			}
			if (x + 1 < N && visited[x + 1][y] == 1 && ice[x + 1][y] != 0) {
				melt1.push(make_pair(make_pair(x + 1, y), 0));
				melt2.push(make_pair(make_pair(x + 1, y), 0));
				visited[x + 1][y] *= -1; status++;
			}
			if (y - 1 >= 0 && visited[x][y - 1] ==1 && ice[x][y - 1] != 0) {
				melt1.push(make_pair(make_pair(x, y - 1), 0));
				melt2.push(make_pair(make_pair(x, y - 1), 0));
				visited[x][y - 1] *= -1; status++;
			}
			if (y + 1 < M && visited[x][y + 1] == 1 && ice[x][y + 1] != 0) {
				melt1.push(make_pair(make_pair(x, y + 1), 0));
				melt2.push(make_pair(make_pair(x, y + 1), 0));
				visited[x][y + 1] *= -1; status++;
			}
		}
		// #이미 나눠져있었는가?
		if (status != count) return 0;

		// # 녹는다.
		while (!melt2.empty()) {
			x = melt2.front().first.first;
			y = melt2.front().first.second;
			melt2.pop();
			melt1.push(make_pair(make_pair(x, y), pole(x, y, N, M)));
		}
		year++;

		// # 반영된다.
		while (!melt1.empty()) {
			x = melt1.front().first.first;
			y = melt1.front().first.second;
			c = melt1.front().second;
			melt1.pop();
			ice[x][y] = (ice[x][y] - c) < 0 ? 0 : (ice[x][y] - c);
			if (ice[x][y] == 0) count--;
			else { xx = x; yy = y; }
		}

		// # 이어진 덩어리인가?
		if (count > 0) {
			melt1.push(make_pair(make_pair(xx, yy), 0));
			visited[xx][yy] *= -1; status = 1;
		}
		else status = 0; // 남은 빙하가 없다면 ,,
		while (!melt1.empty()) {
			x = melt1.front().first.first;
			y = melt1.front().first.second;
			melt1.pop();
			if (x - 1 >= 0 && visited[x - 1][y] == -1 && ice[x - 1][y] != 0) {
				melt1.push(make_pair(make_pair(x - 1, y), 0));
				visited[x - 1][y] *= -1; status++;
			}
			if (x + 1 < N && visited[x + 1][y] == -1 && ice[x + 1][y] != 0) {
				melt1.push(make_pair(make_pair(x + 1, y), 0));
				visited[x + 1][y] *= -1; status++;
			}
			if (y - 1 >= 0 && visited[x][y - 1] == -1 && ice[x][y - 1] != 0) {
				melt1.push(make_pair(make_pair(x, y - 1), 0));
				visited[x][y - 1] *= -1; status++;
			}
			if (y + 1 < M && visited[x][y + 1] == -1 && ice[x][y + 1] != 0) {
				melt1.push(make_pair(make_pair(x, y + 1), 0));
				visited[x][y + 1] *= -1; status++;
			}
		}
		if (status != count) return year;
	}
	return 0;
}
int pole(int x, int y, int N, int M) {
	int count = 0;
	if (x + 1 < N && ice[x + 1][y] == 0)
		count++;
	if (x - 1 >= 0 && ice[x - 1][y] == 0)
		count++;
	if (y + 1 < M && ice[x][y + 1] == 0)
		count++;
	if (y - 1 >= 0 && ice[x][y - 1] == 0)
		count++;
	return count;
}