ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2468.안전영역
    알고리즘/백준 BAEK JOON 2020. 5. 26. 23:01

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

     

    2468번: 안전 영역

    재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 �

    www.acmicpc.net

    나는 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;
    }

     

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

     

    '알고리즘 > 백준 BAEK JOON' 카테고리의 다른 글

    14890.경사로  (0) 2020.05.28
    1697.숨바꼭질  (0) 2020.05.27
    2468.안전영역  (0) 2020.05.26
    1012.유기농 배추  (0) 2020.05.26
    7576.토마토  (0) 2020.05.25
    14502.연구소  (0) 2020.05.25

    댓글 0

Designed by Tistory.