이번에는 백준 2468번 안전 영역 문제를 풀어보았습니다.
이 문제는 비의 높이가 달라질 때마다 물에 잠기지 않는 영역의 개수가 달라지고, 그중 최대값을 구하는 문제입니다.
결국 핵심은 각 비 높이마다 잠기지 않은 칸들로 이루어진 연결된 컴포넌트의 개수를 세는 것이었습니다.
문제 설명
N x N 크기의 지역 높이 정보가 주어집니다.
비가 특정 높이만큼 내리면, 그 높이 이하의 모든 칸은 물에 잠긴다고 가정합니다.
이때 물에 잠기지 않은 칸들끼리 상하좌우로 연결된 영역을 안전 영역이라고 하고,
비의 높이를 바꿔가며 안전 영역의 개수 중 최대값을 구하면 됩니다.
즉, 이 문제는 한 번만 탐색하면 끝나는 것이 아니라,
비의 높이를 여러 경우로 바꿔가며 매번 연결된 영역의 개수를 다시 세어야 하는 문제입니다.
풀이 아이디어
이 문제는 높이 k가 주어졌을 때,
space[i][j] > k인 칸만 안전한 칸으로 보고- 아직 방문하지 않은 안전한 칸에서 DFS를 시작해서
- 연결된 영역 하나를 전부 방문 처리
하는 방식으로 해결할 수 있습니다.
그리고 이 작업을 비의 높이 0부터 최대 높이까지 반복하면서,
매 높이마다 나온 안전 영역 개수 중 최댓값을 갱신하면 됩니다.
즉, 구조적으로는
- 하나의 높이에서 연결된 컴포넌트 개수 세기
- 그걸 모든 비 높이에 대해 반복하기
로 볼 수 있습니다.
코드
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> space;
vector<vector<int>> visited;
int N;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};
void dfs(int y, int x, int water) {
visited[y][x] = 1;
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 || visited[ny][nx] || space[ny][nx] <= water) continue;
dfs(ny, nx, water);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
int max_val = -1;
for (int i = 0; i < N; i++) {
space.push_back(vector<int>());
visited.push_back(vector<int>());
for (int j = 0; j < N; j++) {
int temp;
cin >> temp;
if (temp > max_val) max_val = temp;
space[i].push_back(temp);
visited[i].push_back(0);
}
}
int max_cnt = -1;
for (int k = 0; k <= max_val; k++) {
int cnt = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (space[i][j] > k && !visited[i][j]) {
dfs(i, j, k);
cnt++;
}
}
}
if (cnt > max_cnt) max_cnt = cnt;
fill(visited.begin(), visited.end(), vector<int>(N, 0));
}
cout << max_cnt << '\n';
return 0;
}풀이 흐름
- 지역의 높이 정보를 입력받는다.
- 전체 높이 중 최댓값도 함께 구해둔다.
- 비의 높이를
0부터 최대 높이까지 하나씩 올려가며 반복한다. - 현재 비 높이에서 잠기지 않은 칸(
space[i][j] > k)을 기준으로 전체를 순회한다. - 아직 방문하지 않은 안전한 칸을 만나면 DFS를 수행하고, 안전 영역 개수를 1 증가시킨다.
- 해당 높이에서의 안전 영역 개수를 최댓값과 비교해 갱신한다.
- 다음 비 높이에 대해 다시 탐색할 수 있도록
visited를 전부 0으로 초기화한다. - 모든 높이를 확인한 뒤 최댓값을 출력한다.
구현 포인트
1. 연결된 컴포넌트 개수를 세는 문제
이 문제도 결국은 상하좌우로 이어진 칸들의 묶음을 세는 문제입니다.
그래서 구조적으로는 연결된 컴포넌트 개수 세기와 같습니다.
단, 다른 문제들과 달리 한 번만 세는 것이 아니라
비의 높이를 바꿔가며 매번 다시 계산해야 한다는 차이가 있습니다.
2. DFS 조건에 비 높이 포함하기
DFS에서는 단순히 방문 여부만 보는 것이 아니라,
현재 비 높이보다 높은 칸만 이동할 수 있도록 조건을 걸었습니다.
if (ny < 0 || nx < 0 || ny >= N || nx >= N || visited[ny][nx] || space[ny][nx] <= water) continue;즉,
- 범위를 벗어나면 안 되고
- 이미 방문했으면 안 되고
- 현재 물 높이 이하인 칸도 가면 안 됩니다
이 조건으로 안전한 칸만 탐색할 수 있습니다.
3. 비가 오지 않는 경우도 포함해야 함
이 문제에서 중요한 경계값은 비가 전혀 오지 않는 경우입니다.
그래서 비의 높이를 1부터 시작하는 것이 아니라,
반드시 0부터 시작해야 합니다.
for (int k = 0; k <= max_val; k++)노션에도 적어두신 것처럼,
이 문제는 비가 내리지 않는 경우를 고려해야 한다는 점이 중요했습니다.
즉, 경계값을 놓치면 정답이 달라질 수 있는 문제였습니다.
4. visited 배열 다시 초기화하기
비의 높이가 바뀔 때마다 새로운 탐색을 해야 하므로,
이전 탐색의 방문 정보는 전부 초기화해야 합니다.
fill(visited.begin(), visited.end(), vector<int>(N, 0));이렇게 해서 다음 비 높이에 대해 다시 DFS를 수행할 수 있도록 했습니다.
5. 최대 높이까지만 보면 됨
비의 높이는 굳이 무한히 볼 필요가 없고,
입력된 지역 높이의 최댓값까지만 확인하면 충분합니다.
그래서 입력을 받으면서 최대 높이도 같이 구했습니다.
if (temp > max_val) max_val = temp;이후 0 ~ max_val 범위만 확인하도록 했습니다.
