IMImeamangryang
VelogGitHub
← Blog

ENGINEERING NOTE

[백준] 안전 영역

백준 안전 영역맵의 최대 높이를 구한다.물에 잠기는 높이 h를 0부터 최대 높이까지 변화시키며 반복한다.각 h마다 BFS 혹은 DFS로 잠기지 않은 영역의 개수를 센다.모든 높이에 대해 구한 영역 개수 중 최댓값을 출력한다.

7 min read
코딩테스트

문제 링크

백준 안전 영역

접근 방법

  • 맵의 최대 높이를 구한다.
  • 물에 잠기는 높이 h를 0부터 최대 높이까지 변화시키며 반복한다.
  • 각 h마다 BFS 혹은 DFS로 잠기지 않은 영역의 개수를 센다.
  • 모든 높이에 대해 구한 영역 개수 중 최댓값을 출력한다.

풀이 코드

text
// BFS 풀이 방법
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int N;
const int MAX = 101;
int map[MAX][MAX];
bool visited[MAX][MAX];

int dy[] = { 0,0,-1,1 };
int dx[] = { -1,1,0,0 };
queue<pair<int, int>> q;
vector<int> v; //영역 개수 저장 벡터


int cnt; //영역 개수

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    int maxHeight = -1;
    cin >> N;

	// 맵 입력받기
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];

            // 최대 높이 구하기
            if (map[i][j] > maxHeight) {
                maxHeight = map[i][j];
            }
        }
    }

    // 높이마다 영역 개수 구하기
    for (int h = 1; h <= maxHeight; h++) 
    {
        /*BFS 영역 개수 구하기*/
        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
				// 높이보다 같거나 큰 곳에서 BFS 시작
                if (map[y][x] >= h && !visited[y][x]) {
                    visited[y][x] = true;
                    q.push(make_pair(y, x));

                    while (!q.empty()) {
                        int cury = q.front().first;
                        int curx = q.front().second;
                        q.pop();

                        for (int i = 0; i < 4; i++) {
                            int ny = cury + dy[i];
                            int nx = curx + dx[i];

                            if (ny < 0 || nx < 0 || ny >= N || nx >= N)
                                continue;
                            if (map[ny][nx] >= h && !visited[ny][nx]) {
                                visited[ny][nx] = true;
                                q.push(make_pair(ny, nx));
                            }
                        }
                    }
					// BFS가 끝나면 영역 개수 증가
                    cnt++;
                }
            }
        }

		// 영역 개수 저장
        v.push_back(cnt);

        /*초기화*/
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                visited[i][j] = 0;
            }
        }
        cnt = 0;
    }

	// 영역 개수 중 최대값 출력
    cout << *max_element(v.begin(), v.end());
}

다른 풀이

text
// DFS 풀이 방법
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N;
const int MAX = 101;
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; //영역 개수
int maxHeight = -1;

void DFS(int y, int x, int height) {
    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] >= height && !visited[ny][nx]) {
            visited[ny][nx] = true;
            DFS(ny, nx, height);
        }
    }
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

    cin >> N;

	// 맵 입력받기
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];

            // 최대 높이 구하기
            if (map[i][j] > maxHeight) {
                maxHeight = map[i][j];
            }
        }
    }

    // 높이마다 영역 개수 구하기
    for (int h = 1; h <= maxHeight; h++) 
    {
        /*DFS 영역 개수 구하기*/
        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
				// 높이보다 같거나 큰 곳에서 DFS 시작
                if (map[y][x] >= h && !visited[y][x]) {
                    DFS(y, x, h);
					// DFS가 끝나면 영역 개수 증가
                    cnt++;
                }
            }
        }

		// 영역 개수 저장
        v.push_back(cnt);

        /*초기화*/
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                visited[i][j] = 0;
            }
        }
        cnt = 0;
    }

	// 영역 개수 중 최대값 출력
    cout << *max_element(v.begin(), v.end());
}