2468.안전영역

이번에 풀어볼 문제는 백준의 2468 안전영역이다. BFS, DFS(재귀,스택,큐)로 풀이가 가능하다.

2468번: 안전 영역

나는 BFS를 이용해서 풀이를 진행하였고 난이도는 역시 그렇게 어려운 편은 아니다!!

모든 문제가 그렇지만 설계단계를 잘생각해서 진입해야 헤매지 않고 풀이에 성공할 수 있다.

이 문제는 직전에 포스팅 한 문제들과 다를 바없이 탐색이 문제를 푸는관건이 아니라 탐색 이전까지의 로직을

구현해내는 것이 관건인 문제이다. 이 문제에서는 물에 잠기는 최소높이와 최고높이를 저장한 뒤

최소에서 최고 높이로 점점 물이 차오르는 형식(높이를 추가해주는)으로 구현해야 시간초과를 겪지 않을 수 있다.

굳이 처음부터 탐색하는 것이아니라 차오른 물의 높이를 누적시키면서 탐색하면 된다는 의미이다.

---

* 예를 들어 설명하면 예시로 최소높이:2  최고높이:8인 map이 있다고하자.

로직은 간단하다. 높이가 2인 부분을 "특정숫자 3(마음대로)으로" 표시해두고 나머지는 0으로 만든다.

높이가 2보다 크고 0인 부분만 BFS로 탐색을 한 뒤 true인 부분은 1로 색칠해준다.

( 분할된 영역의 탐색방법은 이전의 유기농 배추에서 배울 수 있으니 참고 )

=> 1. 이게 로직의 한 사이클이 끝난 것이다.

 

=> 2. 그럼  높이를 +1 해준다. 높이는 3이되고 이 3도  "3"으로 표시해준다.

     그 뒤, 나머지 부분은 다시 0으로 표시한 뒤 탐색을 진행하고 영역의 갯수를 카운트한다.

 

=> 3. 영역의 갯수의 최대값을 구하면 끝난다.

---

 

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <algorithm>
#include <queue>
#include <string.h>

#define MAX 101

using namespace std;

int map[MAX][MAX];
int check[MAX][MAX];
int n;
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { 1, -1, 0, 0 };

int answer = 0; // 최대값을 저장할 변수

void search(int a, int b, int c){ // BFS 함수
	check[a][b] = true; // 탐색의 시작점은 체크!
	queue<pair<int, int>> q; // 탐색할 좌표가 저장될 큐
	q.push(make_pair(a, b)); // 해당 좌표를 큐에 담음
	while (!q.empty()){
		int x = q.front().first; // 큐의 x좌표 저장
		int y = q.front().second;// 큐의 y좌표 저장
		q.pop(); // 좌표를 뽑았으니 필요없다. pop!!
		for (int i = 0; i < 4; i++){ 
			int ax = x + dx[i]; //상하좌우 탐색
			int ay = y + dy[i]; //상하좌우 탐색
			if (ax < 0 || ay < 0 || ax >= n || ay >= n) 
				continue; // 맵 내부 영역이 아닐경우 넘어감
			if (check[ax][ay] == 0 && map[ax][ay] > c){ 
				check[ax][ay] = 1; //살아남은 육지로 판명
				q.push(make_pair(ax, ay));//해당좌표로 탐색
			}
		}
	}
}

int main() {
	//freopen("2468.txt", "r", stdin);
	cin >> n;

	int gijun_end = 1;           //최고 높이가 저장될 변수
	int gijun_start = 987654321; //최소높이가 저장될 변수

	for (int i = 0; i < n; i++){
		for (int j = 0; j < n; j++){
			cin >> map[i][j]; //맵 저장
			gijun_end = max(gijun_end, map[i][j]);    // 최고높이
			gijun_start = min(gijun_start, map[i][j]);// 최소높이
		}
	}
	int cnt = 0; // 영역의 갯수가 저장될 변수
	 
	int z = gijun_start; // 시작은 최소 높이로
	if (gijun_start == gijun_end){ // 최고높이와 최소높이가 같으면
		cout << "1" << endl; // 당연히 육지는 1개가 최소다..
		return 0;            //종료
	}

	while (z!=gijun_end){ //물이 최고높이가 될때까지 반복
		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++){
				if (map[i][j] == z){ //물의 높이와 같은 육지는
					check[i][j] = 3; //잠긴다.
				}
				if (check[i][j] == 1)//살아남은 육지가 있다면
					check[i][j] = 0; //육지 탐색 전으로 돌림
			}
		}
        //다시 되돌렸다면 
		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++){
				if (map[i][j] > z && check[i][j]==0){
                	//물보다 높은 곳이면서 탐색하지않은 육지라면
					search(i, j, z); 
                    //해당좌표를 시작으로 육지 탐색
					cnt++; 
                    //탐색 후 살아남은 분할 영역들 카운트
				}
			}
		}
		answer = max(answer, cnt); // 분할 영역들중 최대값 저장
		cnt = 0;// 탐색이 종료되었으니 분할 카운트 초기화
		z++;    // 탐색이 종료되었으니 높이 증가
	}
	cout << answer << "\n";
	return 0;
}

 

# 무슨 문제든 설계가 가장 중요!!