그래프/BFS

빙산

4gats 2023. 5. 25. 18:21

https://www.acmicpc.net/problem/2573

 

2573번: 빙산

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을

www.acmicpc.net

배열의 값을 바꿀 때는 tmp 배열에 옮기는 방법을 떠올리자!!

무턱대고 바꾸면 큰일 난다. 

이 문제에서 board 배열을 임의로 바꿔서

다음 녹는 빙산을 구할 때 바다의 수가 변형되어 버렸다...

 

나머지는 그냥 BFS를 이용하는 것이다...

 

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
#include <iostream>
#include <queue>
#include <cstring>
 
using namespace std;
 
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1,-1, 0,0 };
 
int n, m;
int board[303][303];
int tmp[303][303];
bool check[303][303];
 
int main()
{
    cin >> n >> m;
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            cin >> board[i][j];
    }
    int ans = 0;
 
    while (true)
    {        
        int cnt = 0;
        queue<pair<int, int>> q;
        
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (board[i][j] != 0 && check[i][j] == false)
                {
                    cnt++;
                    check[i][j] = true;
                    q.push(make_pair(i, j));
                    
 
                    while (!q.empty())
                    {
                        int x = q.front().first;
                        int y = q.front().second;
                        q.pop();
 
                        for (int k = 0; k < 4; k++)
                        {
                            int nx = x + dx[k];
                            int ny = y + dy[k];
                            if (nx >= 0 && nx < n && ny >= 0 && ny < m)
                            {
                                if (board[nx][ny] != 0 && check[nx][ny] == false)
                                {
                                    check[nx][ny] = true;
                                    q.push(make_pair(nx, ny));
                                }
                            }
                        }
                    }
                    
                }
            }
        }
 
 
        if (cnt == 0)
        {
            cout << 0 << '\n';
            break;
        }
        else if (cnt >= 2)
        {
            cout << ans << '\n';
            break;
        }
    
        memset(tmp, 0, sizeof(tmp));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (board[i][j] != 0)
                {
                    int sea = 0;
                    for (int k = 0; k < 4; k++)
                    {
                        int ni = i + dx[k];
                        int nj = j + dy[k];
                        if (ni >= 0 && ni < n && nj >= 0 && nj < m)
                        {
                            if (board[ni][nj] == 0)
                                sea++;
                        }
                    }
                    int val = board[i][j] - sea;
                    if (val > 0)
                        tmp[i][j] = val;
                }
            }
        }
 
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
                board[i][j] = tmp[i][j];
        }
 
        memset(check, false, sizeof(check));
        ans++;
    }
 
    return 0;
}
 cs