BaekJoon 2468 안전영역 (BFS)

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

소스 결과 : 1988 KB / 44 ms

문제 출처 : BackJoon, KOI 2010 초등부 2번

 

소스코드 설명

BFS 문제

최대 높이까지 전부 탐색해야 하는 경우

처음에 문제 읽을 때 기준이 몇인지 주어져야 하는데 왜 안주어지나 궁금했던 문제

최대 크기가 100 이기에 인접 행렬을 사용

 

현재 위치를 저장하는 mPoint 구조체를 사용

 

알고리즘

1. 입력 값을 받으면서 최대 높이를 구한다.

2. 0 ~ 최대 높이까지 반복

 2. 1 현재 높이를 기준으로 안전구역 설정

 2. 2 생성된 안전구역을 기준으로 BFS 진행

 2. 3 구해진 안전구역 수를 현재 최대 구역 수와 비교해 최대 구역수를 설정

3. 2에서 얻어진 최대 구역 수를 출력

 

소스코드

#include <iostream>
#include <queue>

using namespace std;

struct mPoint {
	int x;
	int y;

	mPoint() {};
	mPoint(int x, int y) : x(x), y(y) {};
};

const int posX[4] = { 1, 0, -1, 0 };
const int posY[4] = { 0, 1, 0, -1 };

int func(bool zone[100][100], int n)
{
	int fieldCount = 0;

	queue<mPoint> q;
	bool check[100][100];

	for (int i = 0; i < n; i++)
		fill_n(check[i], n, false);

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			if (!zone[i][j] || check[i][j])
				continue;

			q.push(mPoint(i, j));

			while (!q.empty())
			{
				mPoint cur = q.front();
				q.pop();

				if (check[cur.x][cur.y])
					continue;

				check[cur.x][cur.y] = true;

				// check Field
				for (int pos = 0; pos < 4; pos++)
					if (0 <= cur.x + posX[pos] && cur.x + posX[pos] < n && 0 <= cur.y + posY[pos] && cur.y + posY[pos] < n)
					{
						if (zone[cur.x+posX[pos]][cur.y+posY[pos]])
							q.push(mPoint(cur.x + posX[pos], cur.y + posY[pos]));
					}
						
			}

			fieldCount++;
		}
	
	return fieldCount;
}

void checkSafe(const int map[100][100],bool zone[100][100], int n, int water)
{
	for (int i = 0 ; i < n ;i++)
		for (int j = 0; j < n; j++)
		{
			if (map[i][j] <= water)
				zone[i][j] = false;
			else
				zone[i][j] = true;
		}
}

int main()
{
	int maxHeight = 0;
	int maxCount = 0;
	int n;
	int map[100][100];

	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			cin >> map[i][j];
			if (maxHeight < map[i][j])
				maxHeight = map[i][j];
		}
			
	for (int i = 0; i < maxHeight; i++)
	{
		bool safeZone[100][100];
		
		checkSafe(map, safeZone, n, i);

		int safe = func(safeZone, n);
		if (maxCount < safe)
			maxCount = safe;
	}

	cout << maxCount;

	return 0;
}