-

[DFS] 백준 2573번 - 빙산 본문

3. DFS & 백트래킹

[DFS] 백준 2573번 - 빙산

asdklfjlasdlfkj 2020. 2. 7. 16:43

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

 

2573번: 빙산

첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지

www.acmicpc.net

정답률이 26%인 것에 비해서는 기다지 난이도가 있는 문제는 아니다.

이 문제는 시뮬레이션 + DFS 문제로 시간의 흐름에 따라 빙산을 녹여주는 시뮬레이션 코드와

녹은 빙산의 면적이 몇 개의 구역으로 나뉘는 지 DFS로 확인하는 문제다. 물론 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
116
#include <iostream>
#include <vector>
 
using namespace std;
 
int Time = 0;
bool found_answer = false;
int num_glacier = 0;
int N, M;
vector<vector<int> > map, Minus;
vector<vector<bool> > check;
typedef struct dir{
    int dr, dc;
}dir;
dir direction[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
 
void reset(){
    for (int r = 0; r < N; r++){
        for (int c = 0; c < M; c++){
            Minus[r][c] = 0;
            check[r][c] = false;
        }
    }
    num_glacier = 0;
}
 
bool checkAllClear(){
    bool AllClear = true;
    for (int r = 0; r < N; r++){
        for (int c = 0; c < M; c++){
            if (map[r][c]) {
                AllClear = false;
                break;
            }
        }
        if (!AllClear) break;
    }
    return AllClear;
}
 
void dfs(int r, int c){
    check[r][c] = true;
    for (int i = 0; i < 4; i++){
        int nr = r + direction[i].dr;
        int nc = c + direction[i].dc;
        if (nr >= 0 && nr < N && nc >= 0 && nc < M){
            if (!check[nr][nc] && map[nr][nc]){
                dfs(nr, nc);
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    map.assign(N, vector<int>(M, 0));
    Minus.assign(N, vector<int>(M, 0));
    check.assign(N, vector<bool>(M, false));
    for (int r = 0; r < N; r++){
        for (int c = 0; c < M; c++){
            cin >> map[r][c];
        }
    }
    while (!checkAllClear()){
        Time++;
        // 1. 녹는다.
        for (int r = 0; r < N; r++){
            for (int c = 0; c < M; c++){
                if (map[r][c]){
                    int num_sea = 0;
                    for (int i = 0; i < 4; i++){
                        int nr = r + direction[i].dr;
                        int nc = c + direction[i].dc;
                        if (nr >= 0 && nr < N && nc >= 0 && nc < M){
                            if (map[nr][nc] == 0){
                                num_sea++;
                            }
                        }
                    }
                    Minus[r][c] = num_sea;
                }
            }
        }
        for (int r = 0; r < N; r++){
            for (int c = 0; c < M; c++){
                if (map[r][c]){
                    map[r][c] -= Minus[r][c];
                    if (map[r][c] < 0) map[r][c] = 0;
                }
            }
        }
        // 2. 갯수 센다.
        for (int r = 0; r < N; r++){
            for (int c = 0; c < M; c++){
                if (map[r][c] && !check[r][c]){
                    dfs(r, c);
                    num_glacier++;
                }
            }
        }
        if (num_glacier >= 2) {
            found_answer = true;
            break;
        }
        reset();
    }
    if (!found_answer){
        cout << "0\n";
        return 0;
    }
    cout << Time << '\n';
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
 http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs

저작자표시 비영리 변경금지

'3. DFS & 백트래킹' 카테고리의 다른 글

[DFS] 백준 2210번 - 숫자판 점프  (0) 2020.02.07
[백준] 2668번 - 숫자 고르기  (0) 2020.02.07
[DFS/백트래킹] 백준 17136번 - 색종이 붙이기  (0) 2020.01.28
[DFS] 백준 2468번 - 안전영역 (정답률 33%)  (0) 2020.01.13
[DFS] 백준 2583번 - 영역 구하기 (정답률 56%)  (0) 2020.01.13
'3. DFS & 백트래킹' Related Articles more
Comments