[BOJ] 2468번 안전영역 문제풀이 (C++)

2018.1.2에 쓰여진 글입니다.

---

문제링크

https://www.acmicpc.net/problem/2468

2468번: 안전 영역

 

풀이방법

DFS를 연습할수 있는 아주 좋은 문제

 

기본 로직은 다음과 같음

1. 가장 높은 높이를 저장해놓음(max_height)

2. 높이를 1부터 max_height 까지 설정해주면서 각각의 안전영역 개수가 몇개인지 체크

3. 이때 가장 많은 안전영역의 개수를 저장해 놓는다

 

안전영역을 체크할때 재귀함수를 이용한 DFS로 구하면 끝

근데 이걸 BFS로도 접근할수있지 않을까? 그리고 BFS로하면 더 빠르게 풀수있을것같다.

(만약 이글을 보고 계신분이 있다면 BFS로도 풀어보시길..

저는 바빠서.. BFS풀이코드는 다음으로 미루겠음둥..배그해야되서 그런건 비밀)

문제를 풀때는 항상 다양한 방법으로 풀어보는 것이 포인트! 

일단 DFS를 이용한 코드만 올려놓음 ~~ 

 

소스코드

#include <iostream>
#include <algorithm>    //max 위한 헤더
 
using namespace std;
 
int N;                    
int map[100][100];        //맵
bool visited[100][100];    //방문체크
bool area_check;        //영역체크하는함수
int Answer;                //정답
int dx[] = { -1,0,1,0 };//방향설정
int dy[] = { 0,-1,0,1 };
int max_height;            //가장높은 높이 설정
 
void Init_map()        //맵초기화
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            map[i][j] = 0;
}
 
void Init_visited()        //맵초기화
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            visited[i][j] = false;
}
 
void solve(int cur_x, int cur_y, int h)
{
    if (0 <= cur_x&&cur_x < N && 0 <= cur_y&&cur_y < N &&    //범위안에있고
        !visited[cur_x][cur_y]) {        //아직방문안했다면
        visited[cur_x][cur_y] = true;    //방문하자
        if (map[cur_x][cur_y] > h) {    //현재 있는곳이 침수가 안된다면(침수된곳 높이보다 높다면)
            area_check = true;            //이영역은 안전영역으로 체크해준다(true로 바꿈)
            for (int i = 0; i < 4; i++) {    //상하좌우돌리자
                int new_x = cur_x + dx[i];
                int new_y = cur_y + dy[i];
                if (0 <= new_x&&new_x < N && 0 <= new_y&&new_y < N &&
                    !visited[new_x][new_y]) {    //범위안에있고 방문안했다면
                    solve(new_x, new_y, h);        //방문해준다
                }
            }
        }
    }
}
int main()
{
    cin >> N;
    Init_map();            //맵초기화
    Init_visited();        //방문초기화
    Answer = 1;            //정답초기화, 만약 비가안왔을경우에는 1일테니까 1로 초기화
    max_height = 0;        //높이초기화
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];                            //입력을 받으면서 
            max_height = max(max_height, map[i][j]);    //가장큰 높이 저장
        }
    for (int h = 1; h <= max_height; h++) {        //높이가1부터 전부침수될때까지체크하자
        int area_count = 0;        //영역카운트 0으로초기화하면서 선언
        Init_visited();            //방문을 초기화해준다
        
        //각높이마다 영역체크하는함수
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                area_check = false;        //영역체크 false로 해놓고 
                solve(i, j, h);            //해당함수호출
                if (area_check)            //영역체크 true라면 
                    area_count++;        //해당영역 카운트해준다
            }
        }
        Answer = max(Answer, area_count);    //현재높이에서 안전영역갯수와 정답인자 비교. 
                                            //가장큰값저장
        //각높이마다 영역체크하는 함수
    }
    cout << Answer << endl;
 
    return 0;
}