백준 2468_안전 영역 문제풀이 in C++

in Devlog on Algorithm
  1. 문제 URL
  2. 문제 요구사항
  3. 접근 방법
  4. 풀이 순서
  5. 소스코드
  6. 문제 풀이 결과

문제 URL

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

문제 요구사항

  • 첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. (N은 2 이상 100 이하의 정수)
  • 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. (높이는 1이상 100 이하의 정수)
  • 물에 잠기지 않는 안전한 영역의 최대 개수를 구하시오.

접근 방법

  • 기존에 풀었던 단지 번호 붙이기와 비슷하다 생각되어 비슷하게 풀이했다. 다른 점이 있다면, 이 문제는 물에 잠기지 않는 안전한 영역의 최대 개수를 요구한다. 이때, 잠기는 영역을 0부터~맵의 최대 높이 -1까지 반복하여, 안전한 영역의 최대 개수를 구하면 된다. (나는 처음 문제를 잘못 이해해서 N 값을 잠기는 영역(높이)로 설정했다…알고 보니, 최대 개수를 찾는 것,,,)

풀이 순서

  1. N(맵의 크기)를 입력 받는다.
  2. N * N 사이즈의 맵 각각의 지형 높이를 입력 받는다.
  3. 입력과 동시에 가장 높은 높이를 maxHeight 변수에 넣는다.
  4. 삼중 for문을 사용해서 높이만큼 BFS에 조건을 줘 실행한다.
  5. BFS 수행
    • 큐에 시작 위치 x, y를 넣는다.
    • 큐가 비어있을 때까지 while문을 반복한다.
    • 큐에 첫번째 원소 값을 변수(현재 위치)에 저장하고, 해당 값을 큐에서 꺼낸다.
    • 맵의 현재 좌표 값이 인자로 받은 높이보다 크고, 방문하지 않았다면, now_count를 +1하고, 방문 체크를 한 뒤, nx, ny를 구하여 조건에 맞을 시 큐에 넣는다.
    • 이 과정을 반복 수행
  6. BFS가 끝난 후 now_count가 true(양수)면 area_count(삼중 for문에서 해당 높이의 영역 개수)를 +1 한다.
  7. 2개의 for문이 모두 수행 되면 result 값과 비교하여, area_count가 result 값보다 크면 result 값을 갱신해준다.
  8. 이후 이 작업을 반복한다.

소스코드

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

int N;
int dx[] = { 1, 0 , -1, 0 };
int dy[] = { 0, 1, 0, -1 };
int safeZoneMap[100][100];
bool visitedZone[100][100];
int maxHeight = -1;
int result = -1;
int now_count = 0;
int area_count = 0;
void safeZoneBFS(int startX, int startY, int height) {
	queue<pair<int, int>> q;

	q.push( { startX, startY } );

	while (!q.empty()) {
		int xx = q.front().first;
		int yy = q.front().second;

		q.pop();

		if (safeZoneMap[xx][yy] > height && visitedZone[xx][yy] == false) {
			now_count++;
			
			visitedZone[xx][yy] = true;

			for (int i = 0; i < 4; i++) {
				int nx = xx + dx[i];
				int ny = yy + dy[i];

				if (nx >= 0 && ny >= 0 && nx < N && ny < N) {
					q.push({ nx,ny });
				}
			}
		}
	}
}

void safeZone() {
	cin >> N;
	result = -1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> safeZoneMap[i][j];

			if (maxHeight < safeZoneMap[i][j]) {
				maxHeight = safeZoneMap[i][j];
			}
		}
	}

	for (int h = 0; h < maxHeight; h++) {
		area_count = 0;
		memset(visitedZone, false, sizeof(visitedZone));

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (safeZoneMap[i][j] > h) {
					now_count = 0;
					safeZoneBFS(i, j, h);

					if (now_count) {
						area_count++;
					}
				}
			}
		}
		if (area_count > result) {
			result = area_count;
		}
	}
	cout << result;
}

int main() {

	safeZone();

	return 0;
}

문제 풀이 결과