[알고리즘] 백준 2468번: 안전 영역 (C++), 최소 조건을 확인하라

이번 문제에서 크게 어려웠던 점은 없었으나 각 문제에 대한 포인트를 항상 블로그에 담아두려 하기 때문에 가져왔다.

문제에서 헷갈릴 수 있는 건 visited의 리셋이었다.

 

비의 높이에 따라 bfs를 해주며 건물의 개수를 cnt하며 배열에 따로 담았었다. 하지만, cnt를 담은 배열을 디버깅해보니 처음을 제외하고는 전부 0이었다. 이 부분에서 visited를 초기화시키지 않았구나라는 것을 알고 reset 함수를 작성하고, 비에 높이에 따라 건물 cnt가 끝날 때마다 reset 함수를 콜 해주었다.

---

[코드]

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int map[101][101] = { 0, };
bool visited[101][101] = { 0, };
int n;

typedef struct {
	int y, x;
} Direction;

Direction dir[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

void bfs(int row, int col, int rain) {
	queue<pair<int, int>> q;
	q.push(make_pair(row, col));

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;

		q.pop();
		for (int i = 0; i < 4; i++) {
			int dy = y + dir[i].y;
			int dx = x + dir[i].x;
			if (!visited[dy][dx] && map[dy][dx] > rain) {
				visited[dy][dx] = 1;
				q.push(make_pair(dy, dx));
			}
		}
	}
}

void reset() {// visited 전면 초기화
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			visited[i][j] = 0;
		}
	}
}

int main() {
	cin >> n;
	int max = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int idx;
			cin >> idx;
			map[i][j] = idx;
			if (idx > max) {
				max = idx;
			}
		}
	}

	vector<int> cntArr;
	for (int rain = 1; rain <= max; rain++) {
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (!visited[i][j] && map[i][j] > rain) {
					visited[i][j] = 1;
					bfs(i, j, rain);
					cnt++;
				}
			}
		}

		reset();
		cntArr.push_back(cnt);
	}

	sort(cntArr.begin(), cntArr.end());
	cout << cntArr.back();

	return 0;
}

하지만, 이는 76%까지 밖에 가지 못 한다.

이 정도의 퍼센티지라면 논리는 맞으나 어딘가에 반례가 있다고 생각했다.

---

이 문제의 포인트 (이번 포스팅의 이유)

가끔 문제를 풀 때 논리는 맞는 거 같지만 반례가 존재하는 듯 해보일 때는 항상 문제에서 가질 수 있는 최솟값을 먼저 넣어보라는 댓글을 봤었다.

 

이를 기억하고

1
1

값을 넣어준 결과 내가 도출해내려는 값 0이 나오는 것은 틀리지 않았었다.

 

'장마철이라고 해서 당연히 비가 한 방울이라도 오겠지'라는 생각이었다.

하지만, 문제에서 말하는 힌트가 있었다.

'장마철인데 왜..?'라는 생각이 들었지만 이에 따라 코드를 고쳐주었다.

(지금 생각해보니 장마철이라고 다 물에 잠기지는 않네)

그저 for문에서 rain의 시작 값을 1에서 0으로 고쳐주기만 하면 된다.

 

[정답 코드]

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int map[101][101] = { 0, };
bool visited[101][101] = { 0, };
int n;

typedef struct {
	int y, x;
} Direction;

Direction dir[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

void bfs(int row, int col, int rain) {
	queue<pair<int, int>> q;
	q.push(make_pair(row, col));

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;

		q.pop();
		for (int i = 0; i < 4; i++) {
			int dy = y + dir[i].y;
			int dx = x + dir[i].x;
			if (!visited[dy][dx] && map[dy][dx] > rain) {
				visited[dy][dx] = 1;
				q.push(make_pair(dy, dx));
			}
		}
	}
}

void reset() {// visited 전면 초기화
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			visited[i][j] = 0;
		}
	}
}

int main() {
	cin >> n;
	int max = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int idx;
			cin >> idx;
			map[i][j] = idx;
			if (idx > max) {
				max = idx;
			}
		}
	}

	vector<int> cntArr;
	for (int rain = 0; rain <= max; rain++) {
		int cnt = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (!visited[i][j] && map[i][j] > rain) {
					visited[i][j] = 1;
					bfs(i, j, rain);
					cnt++;
				}
			}
		}

		reset();
		cntArr.push_back(cnt);
	}

	sort(cntArr.begin(), cntArr.end());
	cout << cntArr.back();

	return 0;
}