백준 2468번 안전 영역

문제 링크입니다: https://www.acmicpc.net/problem/2468

DFS(Depth First Search) 혹은 BFS(Breadth First Search) 알고리즘을 적용하여 풀 수 있는 문제였습니다.

물에 잠기는 높이가 주어지지 않았기 때문에 1~100까지 모두 살피면서 연결된 요소들의 개수 즉, Component 최대 개수를 Brute Force 방식으로 찾아봐야하는 문제였습니다.

copy 함수를 통해 물에 잠기지 않는 높이만 area 배열에서 temp 배열로 복사하고 DFS를 통해 Component 개수를 찾아보면 되는데 한 가지 주의할 점은 최소 연결 요소는 1이기 때문에 처음에 result=1로 초기화 한 상태에서 max(result, cnt);를 통해 최대 연결 요소 개수를 구해야합니다!

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100;

 

typedef struct

{

        int y, x;

}Dir;

 

Dir moveDir[4] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

 

int N;

int area[MAX][MAX];

int temp[MAX][MAX];

bool visited[MAX][MAX];

 

//물에 잠기지 않는 높이만 temp에 복사

void copy(int depth)

{

        for (int i = 0; i < N; i++)

                 for (int j = 0; j < N; j++)

                         if (area[i][j] > depth)

                                 temp[i][j] = area[i][j];

}

 

//전형적인 DFS

void DFS(int y, int x)

{

        visited[y][x] = true;

 

        for (int i = 0; i < 4; i++)

        {

                 int nextY = y + moveDir[i].y;

                 int nextX = x + moveDir[i].x;

 

                 if (0 <= nextY && nextY < N && 0 <= nextX && nextX < N)

                         if (!visited[nextY][nextX] && temp[nextY][nextX])

                                 DFS(nextY, nextX);

        }

}

 

int main(void)

{

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 for (int j = 0; j < N; j++)

                         cin >> area[i][j];

 

        int result = 1;

        //물에 잠기는 높이 1~100

        for (int depth = 1; depth <= MAX; depth++)

        {

                 memset(visited, false, sizeof(visited));

                 memset(temp, 0, sizeof(temp));

                 copy(depth);

 

                 //Component 최대 개수 구한다

                 int cnt = 0;

                 for (int i = 0; i < N; i++)

                         for (int j = 0; j < N; j++)

                                 if (!visited[i][j] && temp[i][j])

                                 {

                                          DFS(i, j);

                                          cnt++;

                                 }

                 result = max(result, cnt);

        }

 

        cout << result << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~