백준 안전 영역(2468) C++ 풀이

알고리즘 영역

그래프 이론

브루트포스 알고리즘

그래프

너비 우선 탐색

깊이 우선 탐색

문제해결 아이디어

잠기는 영역들은 미리 방문 처리를 하고, DFS(깊이 우선 탐색)을 통해 각각의 연결된 영역들을 체크하여 개수를 세면 된다.

코드

#include <iostream>
using namespace std;


int n; // 행과 열의 개수
int arr[101][101]; // 비의 양을 저장하는 2차원 배열
bool visited[101][101]; // 방문했는가?를 판단하는 2차원 배열
int maxH = 0; // 입력된 비의 양의 최대
int maxCnt = 0; // 안전한 영역의 최대 개수
int cnt = 0; // 안전한 영역을 세는 변수

// 상하좌우 세팅
int dirX[] = { -1,1,0,0 };
int dirY[] = { 0,0,-1,1 };

void dfs(int y, int x)
{
    // 방문 처리
	visited[y][x] = true;

    // 상하좌우 체크
	for (int i = 0; i < 4; i++)
	{
		int _y = dirY[i] + y;
		int _x = dirX[i] + x;
         
        // 범위를 안 넘어서면
		if (_y >= 0 && _y < n && _x >= 0 && _x < n)
		{
			if (!visited[_y][_x])
				dfs(_y, _x);
		}
	}
	
}

int main()
{
	cin >> n;
    

   // 비의 양 입력
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> arr[i][j];
            // 최대 비의 양 체크
			if (maxH < arr[i][j]) maxH = arr[i][j];
		}
	}
    
   // 안전한 영역 구하기 계산
	for (int i = 0; i <= maxH; i++)
	{
       // 초기화
		cnt = 0;
        
        // 잠긴 영역 => 방문처리
		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < n; k++)
			{
				if (arr[j][k] <= i)
					visited[j][k] = true;
				else
					visited[j][k] = false;
			}
		}
        
        //브루트포스(완전탐색)
		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < n; k++)
			{
               // 방문하지 않았다면(DFS로 탐색 필요)
				if (!visited[j][k])
				{
					dfs(j, k);
                    // 횟수 증가
					cnt++;
				}
			}
		}

		if (maxCnt < cnt)
			maxCnt = cnt;
	}

	cout << maxCnt;
}

코드 설명

단순히 잠기는 곳은 이미 방문했다 생각하고, 안 잠기는 곳은 미방문처리하여 DFS를 통해 상하좌우 탐색을 하여 이어져 있는 것을 한 블럭으로 생각하여 Count를 세면 되는 문제였다.