(C++) 백준 2468번 [안전 영역]

안녕하세요 평범한 컴공생입니다!

 

백준 2468번 문제 [안전 영역] 알고리즘 포스팅을 시작해보겠습니다.

BFS 문제라서 풀어보려 했던 것이었는데 DFS로 해결을 했습니다. 아직 자료구조들의 명확한 차이와 정확한 이해는 쉽지 않은 것 같습니다.

실버 1 난이도의 문제입니다

1. 문제 해결 방법 구상하기

 -  비의 높이는 아예 비가 안오는 경우부터 비로 인해 모든 영역이 다 잠기는 경우까지 사이에 있는 값들이 될 수 있습니다.

 - 그 경우들을 하나 하나 해보면서 가장 안전한 영역이 많을 때를 갱신해줍니다.

 - height 이차원 배열의 어느 한 지점으로부터 동서남북 네 가지 방향 중 하나를 탐색해주기 위하여 dr, dc의 배열을 선언해줍니다.

 - 그 다음 탐색 지점이 필드 안의 값이 아니라면(0보다 작거나 N-1 보다 크면) 다음 명령문을 진행해주지 않고, 안전한 영역들만 탐색해줄 것이기 때문에 안전한 영역이 아니거나, 이미 한 번 탐색을 진행했던 지점이라면 중복탐색을 하지 않아야 합니다.

 - 이중반복문을 통해 모든 지점을 다 탐색시작지점으로 하여 돌려봅니다. (이 때, 이미 탐색했던 지점이거나 안전하지 않은 영역이면 안됩니다.)

 

2. 구상한 아이디어를 바탕으로 코딩하기

#include <iostream>
#include <algorithm>
#include <cstring>

int height[100][100]; // 필드값을 입력받기 위한 배열
bool check[100][100]; // 탐색을 했던 지점인가를 확인하기 위한 배열
int N;
int max_Height = -987654321; // 가장 높은 지점까지 모든 경우의 수를 돌려야하므로 필요
int max_Safeplace = -987654321; // 안전영역의 수
int cnt;

using namespace std;

//구조체로 구현해도 됨. 동서남북 탐색을 위한 도구
int dr[4] = { 0, 0, 1, -1 };
int dc[4] = { 1, -1, 0, 0 };

void DFS(int r, int c, int rain) {
	for (int i = 0; i < 4; i++) {
		int next_r = r + dr[i];
		int next_c = c + dc[i];

		if (next_r < 0 || next_c < 0 || next_r >= N || next_c >= N) continue;
		if (height[next_r][next_c] <= rain || check[next_r][next_c]) continue;

		check[next_r][next_c] = true;
		DFS(next_r, next_c, rain);
	}
}

void input()
{
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
		{
			cin >> height[i][j];
			if (height[i][j] > max_Height)
				max_Height = height[i][j]; // 최고 높이를 구하여야 모든 경우를 돌려볼 수 있음.
		}
}

void solve()
{
	for (int rain = 0; rain <= max_Height; rain++)
	{
		cnt = 0;
		memset(check, 0, sizeof(check));
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
			{
				if ((check[i][j] == false) && (height[i][j] > rain))
				{ // 그 지점을 아직 탐색하지 않았어야 하고, 안전한 영역이어야 함.
					cnt++;
					DFS(i, j, rain);
				}
				else
					check[i][j] = true;
			}
		max_Safeplace = max(max_Safeplace, cnt);
	}
}

void output()
{
	cout << max_Safeplace << endl;
}

int main()
{
	input();
	solve();
	output();
}

 

DFS 는 다음 탐색을 들어가기 위한 조건들을 잘 세워두지 않으면 중복이 생기거나 탐색이 완전히 꼬여버릴 수 있는 것 같다. 항상 그 조건을 먼저 잘 설계하고 DFS 함수를 구현하도록 해야겠다.

 

/ /문제제기 및 피드백 언제든지 감사히 받겠습니다.