[백준] 2468번 안전 영역

문제 링크

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

 

문제 해설

단지 번호 붙이기와 많이 비슷하다. 3차 반복문으로 해서 가장 바깥 반복문은 강수량이 0부터 최대값까지 해서 경우의 수를 구한다. 최대값은 100으로 해도 될 수 있는데 굳이 불필요하게 순회하기 싫어서 max_height를 구해 거기까지만 순회하도록 했다.

 

전체 코드

 

#include <iostream>
#include <array>
using namespace std;

array<array<int, 100>, 100> map;
array<array<bool, 100>, 100> visited;

int N;

void dfs(int row, int col, int height);
void init_visited();

int adj_row[] = { 1, 0, -1, 0 };
int adj_col[] = { 0, 1, 0, -1 };

int main()
{	
	for (int i = 0; i < 100; ++i)
		map[i].fill(0);

	cin >> N;
	int max_height = -1;
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
		{
			int height;
			cin >> height;
			map[i][j] = height;

			if (height > max_height)
				max_height = height;
		}

	int max = -1;
	for (int height = 0; height <= max_height; ++height)			
	{
		int count = 0;
		init_visited();

		for (int i = 0; i < N; ++i)
		{
			for (int j = 0; j < N; ++j)
			{
				if (visited[i][j] == false && map[i][j] > height)
				{
					++count;
					dfs(i, j, height);
				}
			}
		}		
		
		if (max < count)
			max = count;		
	}

	cout << max << endl;
}

void dfs(int row, int col, int height)
{
	visited[row][col] = true;

	for (int i = 0; i < 4; ++i)
	{
		int next_row = row + adj_row[i];
		int next_col = col + adj_col[i];

		if (next_row < 0 || next_row >= N || next_col < 0 || next_col >= N)
			continue;
			
		if (false == visited[next_row][next_col] && map[next_row][next_col] > height)
			dfs(next_row, next_col, height);
	}
}

void init_visited()
{
	for (int i = 0; i < 100; ++i)
		visited[i].fill(false);
}