[백준][bfs] 2468 안전 영역 c++ 구현

목차

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

2468번: 안전 영역

문제

 

문제 구현 방향

물에 잠기지 않는 영역을 세어주는 방식으로 구현했다.

bfs를 여러번 돌리면 쉽게 풀리는 문제이다.

 

 

문제 구현시 주의점

빗물 높이가 0인 경우도 있다는 점을 주의해야 한다.

 

 

 

코드 구현

#include <iostream>
#include<stack>
#include<queue>
#include<algorithm>



using namespace std;
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };
int board[101][101] = { 0 };
int visit[101][101] = { 0 };
int N;

void bfs(int start_x, int start_y, int stand) {   // bfs
    queue<pair<int, int>> q;
    q.push(make_pair(start_x, start_y));
    visit[start_y][start_x] = 1;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int new_x = x + dx[i];
            int new_y = y + dy[i];
            if (new_x < 0 || new_x > N- 1 || new_y < 0 || new_y > N - 1)
                continue;
            if (visit[new_y][new_x] || board[new_y][new_x] <= stand)   //빗물이하의 높이일 경우 탐색안함
                continue;
            q.push(make_pair(new_x, new_y));
            visit[new_y][new_x] = 1;
        }
    }

}

int main()
{
    int  i, j, mcnt=0;
    cin >> N;
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }
    
   
    for (i = 0; i < 101; i++) {   //빗물 높이 순서대로 방문
       int  cnt = 0;
        for (int k = 0; k < N; k++) {     
            for (int p = 0; p < N; p++) {
                if (board[k][p] > i && visit[k][p] ==0) {       // 방문안했거나 빗물 높이보다 높을 경우 탐색
                    cnt++;
                    bfs(p, k, i);
                }
            }
        }

        fill(&visit[0][0], &visit[0][0] + 101 * 101, 0);   //방문 초기화
        mcnt = max(mcnt, cnt);    //max갱신
    }
         
     
    cout << mcnt;
        return 0;
      
    }