안전 영역
문제: 안전 영역 (백준 2468번)
구조 분석
해당 문제는 연구소(백준 14502번)문제와 매우 유사한 문제이다. 이는 해당 문제와 동일하게 두 가지 큰 알고리즘이 합쳐진 문제이다.
- 물이 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽, 외쪽으로 인점해 있으며 그 크기가 최대인 영역을 만한다.
- 이는
BFS
나DFS
를 사용하여 해결할 수 있다. DFS
를 이용하여 안전 영역 덩어리를 세는 경우stack
을 이용하면 된다.
- 이는
- 어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 여역의 최대 개수를 구하여라
- 이는
Brute force
로 해결할 수 있다. - 비가 와서 잠길 수 있는 모든 높이에 대해 탐색을 시행하면 된다.
정리해보면 다음과 같다. 우선Brute force
를 이용해 비가 와서 잠기는 모든 높이에 대해 반복문을 돌린다. 그리고 해당 반복문 안에서BFS
나DFS
를 통해 안전 영역 덩어리를 세어 최대값을 반환하면 된다.
- 이는
풀이 방법
이는 최근에 한 번 접해본 유형이어서 크게 당황하지 않고 풀 수 있었다. 구조 분석에서 기술한 바와 같이 풀이를 실시했으며 이번에는 DFS
를 이용해 탐색을 수행했다.
해당 풀이에서 안전 영역 덩어리를 세는 과정에서 큰 어려움이 있었다. 처음에는 잠긴 영역: 0
, 안전 영역: 1
로 설정한 뒤 방문한 영역에 대해서 고려하지 않아 계속해서 틀렸다. 또한 잠기는 영역이 없는 코너 케이스를 고려하지 않아서 애먹었다. 이를 해결하기 위해서 잠긴 영역: 0
, 안전 영역: 1
, 방문 영역: -1
로 표기했고, 코너 케이스 고려하여 stack에서 pop할 때 count를 증가시키고, expand를 실시할 때 인접한 영역을 방문했다면 count를 뺴는 방식으로 수정했다. 또한 시작 카운터를 1로 설정해 아무 지역도 잠기지 않는 경우에 대해 코너 케이스 처리를 했다.
코드
#include <stdio.h>
#include <iostream>
#include <stack>
#define MAX(a,b) (a>b?a:b)
using namespace std;
int n;
int ans = 1;
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
int map[100][100];
int tmp[100][100];
void copy(int map[100][100], int tmp[100][100]) {
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
tmp[i][j] = map[i][j];
}
}
}
void rainDFS(int h) {
stack<pair<int,int>> S;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (tmp[i][j] <= h) {
// Check Unsafe
tmp[i][j] = 0;
}
else {
// Check Safe
tmp[i][j] = 1;
S.push(make_pair(i,j));
}
}
}
int cnt = 0;
while (!S.empty()) {
int x = S.top().first;
int y = S.top().second;
S.pop();
if (tmp[x][y] == -1) continue;
// Check visited
tmp[x][y] = -1;
cnt++;
int flag = 0;
for (int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (0<=nx && nx<n && 0<=ny && ny<n) {
if (tmp[nx][ny] == 1) {
S.push(make_pair(nx,ny));
}
else if (tmp[nx][ny] == -1) {
flag = 1;
}
}
}
if (flag == 1) cnt--;
}
ans = MAX(ans, cnt);
}
int main() {
cin >> n;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
cin >> map[i][j];
}
}
for (int i=1; i<=100; i++) {
copy(map, tmp);
rainDFS(i);
}
cout << ans << "\n";
return 0;
}
정리
문제 구조 분석보다 코너 케이스 때문에 더 애먹었던 문제이다. 일반적으로 BFS나 DFS 문제는 방문 여부를 저장하기 위한 matrix를 추가로 만들어주지만, 한번에 처리하려고 시도했더니 조건문과 코너 케이스에 부딪쳐 고생했다.
댓글남기기