백준 2573번: 빙산 / C++
2023. 3. 24. 00:16ㆍ개인공부/코딩테스트
2573번: 빙산
첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을
www.acmicpc.net
BFS를 응용한 문제로 처음에 10번안에 빙하가 다 녹는다고 생각해서 코드를 작성했는데 아닌 문제였기 때문에 다시 코드를 작성했다.
|
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
|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, M; // row, col
int arr[300][300]{};
int tmp[300][300]{};
int Row = 0 , Col = 0;
void update()
{
for (int row = 1; row < N - 1; ++row)
for (int col = 1; col < M- 1; ++col)
{
if (arr[row][col] != 0)
{
int next = arr[row][col];
// up row-1
if (next > 0 && arr[row - 1][col] == 0)
--next;
// down row+1
if (next > 0 && arr[row + 1][col] == 0)
--next;
// left col-1
if (next > 0 && arr[row][col - 1] == 0)
--next;
// right col+1
if (next > 0 && arr[row][col + 1] == 0)
--next;
tmp[row][col] = next;
}
else
tmp[row][col] = 0;
}
for (int row = 1; row < N - 1; ++row)
for (int col = 1; col < M - 1; ++col){
arr[row][col] = tmp[row][col];
if (arr[row][col] != 0){
Row = row; Col = col;
}
}
}
bool BFS(int row, int col)
{
queue<pair<int, int>> Q;
Q.push(make_pair(row, col));
bool Visitied[300][300]{};
Visitied[row][col] = true;
while (!Q.empty()){
int NowRow =Q.front().first;
int NowCol = Q.front().second;
// up row-1
if (Visitied[NowRow - 1][NowCol] == false && arr[NowRow - 1][NowCol] != 0) {
Q.push(make_pair(NowRow - 1, NowCol));
Visitied[NowRow - 1][NowCol] = true;
}
// down row+1
if (Visitied[NowRow + 1][NowCol] == false && arr[NowRow + 1][NowCol] != 0) {
Q.push(make_pair(NowRow + 1, NowCol));
Visitied[NowRow + 1][NowCol] = true;
}
// left col-1
if (Visitied[NowRow][NowCol - 1] == false && arr[NowRow][NowCol - 1] != 0) {
Q.push(make_pair(NowRow, NowCol - 1));
Visitied[NowRow][NowCol - 1] = true;
}
// right col+1
if (Visitied[NowRow][NowCol + 1] == false && arr[NowRow][NowCol + 1] != 0) {
Q.push(make_pair(NowRow, NowCol + 1));
Visitied[NowRow][NowCol + 1] = true;
}
Q.pop();
}
for(int i=1; i<N-1; ++i)
for (int j = 1; j < M - 1; ++j){
if (Visitied[i][j] == false && arr[i][j] != 0)
return false;
}
return true;
}
void Solve(){
int ans = 0;
while (true)
{
++ans;
Row = 0; Col = 0;
update();
if (Row == 0 && Col == 0){
cout << '0';
return;
}
else{
if (!BFS(Row, Col)){
cout << ans;
return;
}
}
}
}
int main()
{
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
cin >> N >> M;
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
cin >> arr[i][j];
Solve();
}
|
cs |
'개인공부 > 코딩테스트' 카테고리의 다른 글
| 백준 4779번 : 칸토어 집합 / C++ (0) | 2023.03.27 |
|---|---|
| 백준 2638번 : 치즈 / C++ (0) | 2023.03.24 |
| 백준 2589번 : 보물섬 / C++ (0) | 2023.03.23 |
| 백준 11657번 : 타임머신 / C++ (0) | 2023.03.22 |
| 백준 9370번 : 미확인 도착지 / C++ (0) | 2023.03.21 |