ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2468번 안전영역 | BFS, DFS | 백준 2468 C++ 코드
    [백준 알고리즘]/[C++] 2021. 3. 2. 10:04
    728x90
    반응형

     

     

    이번 포스팅은 백준 2468번 안전영역입니다.

    아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

    www.acmicpc.net/problem/2468

     

    2468번: 안전 영역

    재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는

    www.acmicpc.net

     

     

    기본 알고리즘

    BFS 너비 우선 탐색

    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
    //백준2468 안전영역                                                                
     
    #include <iostream>
    #include <queue>
    #include <vector>
    #include <algorithm>
    using namespace std;
     
    int N;
    const int MAX = 101;
    int input[MAX][MAX];
    int map[MAX][MAX];
    bool visited[MAX][MAX];
    int dy[] = { 0,0,-1,1 };
    int dx[] = { -1,1,0,0 };
    queue<pair<intint>> q;
    vector<int> v; //영역 개수 저장 벡터
    int cnt; //영역 개수
     
    void BFS(int y, int x) {
        visited[y][x] = true;
        q.push(make_pair(y, x));
     
        while (!q.empty()) {
            y = q.front().first;
            x = q.front().second;
            q.pop();
     
            for (int i = 0; i < 4; i++) {
                int ny = y + dy[i];
                int nx = x + dx[i];
     
                if (ny < 0 || nx < 0 || ny >= N || nx >= N)
                    continue;
                if (map[ny][nx] && !visited[ny][nx]) {
                    visited[ny][nx] = true;
                    q.push(make_pair(ny, nx));
                }
            }
        }
    }
     
    void reset() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = 0;
                visited[i][j] = 0;
            }
        }
        cnt = 0;
    }
     
    int main() {
        int maxHeight = -1;
        cin >> N;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> input[i][j];
                if (input[i][j] > maxHeight) {
                    maxHeight = input[i][j];
                }
            }
        }
     
        for (int h = 1; h <= maxHeight; h++) {
            /*h미만 물에 잠김*/
     
            /*h미만=0 h이상=1 */
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (input[i][j] < h) {
                        map[i][j] = 0;
                    }
                    else {
                        map[i][j] = 1;
                    }
                }
            }
     
            /*BFS 영역 개수 구하기*/
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] && !visited[i][j]) {
                        BFS(i, j);
                        cnt++;
                    }
                }
            }
            v.push_back(cnt);
            
            /*초기화*/
            reset();
        }
     
        sort(v.begin(), v.end()); //오름차순 정렬
        cout << v[v.size() - 1];  //최댓값 출력
    }
    cs

     

     

     

    DFS 깊이 우선 탐색

     

    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
    //백준2468 안전영역                                                                
     
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
     
    int N;
    const int MAX = 101;
    int input[MAX][MAX];
    int map[MAX][MAX];
    bool visited[MAX][MAX];
    int dy[] = { 0,0,-1,1 };
    int dx[] = { -1,1,0,0 };
    vector<int> v; //영역 개수 저장 벡터
    int cnt; //영역 개수
     
    void DFS(int y, int x) {
        visited[y][x] = true;
     
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
     
            if (ny < 0 || nx < 0 || ny >= N || nx >= N)
                continue;
            if (map[ny][nx] && !visited[ny][nx]) {
                visited[ny][nx] = true;
                DFS(ny, nx);
            }
        }
    }
     
    void reset() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = 0;
                visited[i][j] = 0;
            }
        }
        cnt = 0;
    }
     
    int main() {
        int maxHeight = -1;
        cin >> N;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cin >> input[i][j];
                if (input[i][j] > maxHeight) {
                    maxHeight = input[i][j];
                }
            }
        }
     
        for (int h = 1; h <= maxHeight; h++) {
            /*h미만 물에 잠김*/
     
            /*h미만=0 h이상=1 */
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (input[i][j] < h) {
                        map[i][j] = 0;
                    }
                    else {
                        map[i][j] = 1;
                    }
                }
            }
     
            /*DFS 영역 개수 구하기*/
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] && !visited[i][j]) {
                        DFS(i, j);
                        cnt++;
                    }
                }
            }
            v.push_back(cnt);
            
            /*초기화*/
            reset();
        }
     
        sort(v.begin(), v.end()); //오름차순 정렬
        cout << v[v.size() - 1];  //최댓값 출력
    }
    cs

     

     

     

     

    728x90
    반응형

    댓글

S.B. All Rights Reserved.