[Silver I] 안전 영역 - 2468

[Silver I] 안전 영역 - 2468

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

DFS를 이용해서 풀게 된 문제입니다.

가중치가 적용된 그래프여서 그래프 배열의 초기화는 진행하지 않았습니다.

물의 높이에 따라서 물에 잠기지 않는 안전한 영역의 개수를 카운트해서 최대 개수를 계산하는 프로그램이라

높이 값을 기준으로 DFS를 실행시켰습니다.

물의 높이 값은 입력된 가중치의 최댓값을 기준으로 0부터 확인했습니다.

[Silver I] 안전 영역 - 2468 풀이코드

#include <bits/stdc++.h>
using namespace std;

const int max_n = 104;
int n, maxValue, a[max_n][max_n], visited[max_n][max_n], nx, ny, ret, maxRet;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

void dfs(int y, int x, int height)
{
	visited[y][x] = 1;
	for (int i = 0; i < 4; i++)
	{
		ny = y + dy[i];
		nx = x + dx[i];
		if (ny < 0 || nx < 0 || ny >= n || nx >= n) continue;
		// 물의 높이보다 높으면서 방문하지 않는 노드 확인
		if (a[ny][nx] > height && !visited[ny][nx])
		{
			dfs(ny, nx, height);
		}
	}
	return;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> a[i][j];
			// 입력된 가중치의 최댓값 계산
			maxValue = max(maxValue, a[i][j]);
		}
	}
	
	// 최댓값 가중치를 기준으로 물의 높이 별로 DFS
	for (int h = 0; h < maxValue; h++) 
	{
		ret = 0;
		fill(&visited[0][0], &visited[0][0] + max_n * max_n, 0);
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (a[i][j] > h && !visited[i][j]) 
				{
					ret++; dfs(i, j, h);	
				}
			}
		}
		// 물의 높이에 따라서 최대 안전 영역 저장
		maxRet = max(ret, maxRet);
	}
	
	cout << maxRet;
	
	return 0;
}