백준 2468번 - 안전영역

C++

2468번 - 안전영역

문제 출처

문제

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

접근 방법 및 구현

백준 1012 - 유기농 배추를 응용하여 풀었던 문제다. 물의 높이를 1부터 점점 최고 수위까지 높인다. 각 수위 마다 그 수위보다 같거나 낮은 지대는 잠기게 만든다 이는 visited 의 1을 넣는다. visited로 잠기는 것과 방문하는 것을 동시에 계산한다.

이후 모든 좌표를 하나씩 방문하며 drown 함수에 넣는다. drown 함수는 해당하는 좌표가 물에 잠겼는지 판단하며, 잠기지 않았다면 주위 잠기지 않은 좌표들을 잠기게(방문했다)한다. drown 함수의 리턴 값은 하나라도 잠기지 않은 지역있을 시에 true를 반환하여 count를 1을 올린다. 이를 안전한 영역을 하나 찾은 걸로 표시한다.

이를 통해 수위를 1에서 부터 끝까지 최고 수위까지 올려보며 안전 영역의 수를 찾는다.

여기서 만약 모든 좌표의 값이 1이면, 위의 계산으로는 0이 나오는데 왜냐하면 물의 높이가 1에서 시작해 다 잠기는 것으로 생각하기 때문이다. 이를 방지하기 위해 초기 answer의 값은 1로 하여, 안전영역은 default로 1이라고 설정하면 예외는 없다.

코드

#include <iostream>
#include <vector>

using namespace std;


int n;
int graph[100][100];
bool visited[100][100];
bool Drown(int, int);
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	int max = 0;
	//input으로 좌표를 넣으며, 최고 수위를 찾음.
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> graph[i][j];
			if (max < graph[i][j])
				max = graph[i][j];
		}
	}
	int answer = 1;
	int cnt = 0;
	//물의 높이가 1씩 증가한다. = wl (water level)
	for (int wl = 1; wl < max; wl++) {
		//해당 수위보다 낮은 지역은 물에 잠긴다.
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (graph[i][j] <= wl)
					visited[i][j] = 1;
				else
					visited[i][j] = 0;
			}
		}
		//그래프의 모든 좌표 중 물에 안 잠긴 부분을 탐색
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				//Drown 함수에 각 좌표를 넣고, 하나라도 잠겨 있지 않으면 true -> count 증가
				if (Drown(i, j)) {
					cnt++;
				}
			}
		}
		if (answer < cnt) {
			answer = cnt;
		}
		cnt = 0;
	}
	cout << answer;
	return 0;
}

bool Drown(int y, int x) {
	bool ans = false;
	if (y == -1 || y == n || x == -1 || x == n) {
		return ans;
	}
	//상하좌우 방문하면서 0으로 바꾸어 방문하였다는 것을 표시한다.
	if (visited[y][x] == 0) {
		visited[y][x] = 1;
		Drown(y - 1, x);
		Drown(y + 1, x);
		Drown(y, x - 1);
		Drown(y, x + 1);
		ans = true;
	}

	return ans;
}

후기 및 개선할 점

후기:

처음에는 BFS로 풀려고 알고리즘을 짜보다, 안전항 영역의 수를 찾을 수 없다는 것을 판단하여 DFS인 이전에 풀었떤 알고리즘을 가져와 풀었다. 모든 좌표의 값이 1인 케이스를 판단하지 못하여 틀렸습니다가 나와 고민을 조금 하였다.