2468. 안전 영역

단순 완전탐색보다는 조금 힘든 문제인 것 같다. 

 

Solution 

 

1. 먼저 데이터를 받아 map를 만든다.
2. 여기서 min_high와 max_high를 찾는다. 이는 처음 물높이를 설정할 때 이용한다. 
3. 모든 점을 우선순위 큐에 넣어서 오름차순 정렬을 한다. => 여기서 다른 구조를 사용해도 된다. 나는 벡터를 쓸려고하다가 큐가 편할 것 같아서 큐를 사용했는데 정렬이 안되서 할 수 없이 우선순위 큐를 이용했다. 그러므로 아무 자료구조를 사용해도 좋다. 단, 구조체 정렬이 가능해야된다는 점을 유의하자. 자료량이 계속 들어오는게 아니라 자료량의 크기도 정해져있기 때문에배열도 상관없다. 
4. 높이 가장 작은 곳을 찾아 물 높이가 min_high일 때, 잠기는 지 확인하다. 
5. 잠긴다면, 잠겼다는 표시로 0으로 바꿔준다. 
6. 만약 잠기지 않는다면, 조금 복잡하다. 잠기지 않는다는 말은 이제 물높이가 min_high일 때, 잠길 곳이 없다는 것이다. 그렇기에 완전탐색을 이용하여 현재 안전구역을 탐색해줘야한다. 
7. 안전구역탐색은 현재 남아있는 큐를 또 다른 큐에 복사한다. 이는 k큐로 pop()를 할 때, stack큐에 영향을 안가게 할려고 하는 것이다. 그래서 k큐가 다 없어질 때까지 완전탐색을 하면 된다. 
8. 탐색 결과로 최댓값인지 확인하면된다. 

Key Point

배열의 경우, 함수 매개변수로 넘겨 연산을 하게 될 경우, 원본 데이터에 영향을 끼친다. 그렇기에 원본 데이터가 보존되어야된다면, 데이터를 복사하여야한다. 이는 초보적인 실수임과 동시에 오랜만에 코딩을 할 경우, 생길 수 있는 오류이다. 

어려웠던 점

1. 자료구조를 제대로 파악하지 못해 큐가 인덱스 접근이 불가능한다는 것을 알지 못했다. 급하게 다른 자료구조를 사용했다. 이러한 과정은 코드 수정을 해야되는데 이 과정에서 오류를 많이 발생시킨다. 
2. 큐를 복사하는 과정에서 논리적 오류가 발생하였다. 잠기지 않는 곳일 경우 큐를 복사하고 pop해야되는데 pop부터하여 오류를 찾는데 많은 시간이 걸렸다. 

 

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include<algorithm>
using namespace std;
typedef struct A {
	int high;
	int i;
	int j;
};
int dx[] = { 0,-1,0,1 };
int dy[] = { -1,0,1,0 };
int map_size = 0;

int map[110][110] = { 0 };
struct compare {
	bool operator()(A& I, A& C) {
		if (I.high != C.high)
			return I.high > C.high;
		return I.high < C.high;
	
	}

};
void dfs(int i, int j,int m[][110]){
	m[i][j] = 0;
	for (int k = 0; k < 4; k++) {
		if (i + dx[k] >= 0 && i + dx[k] < map_size && j + dy[k] >= 0 && j + dy[k] < map_size) {
			if (m[i + dx[k]][j + dy[k]] != 0) {
				dfs(i + dx[k], j + dy[k],m);
			}
		}
	}
}
int main(void) {
	freopen("inp.inp", "r", stdin);
	freopen("out.out", "w", stdout);


	cin >> map_size;
	priority_queue<A,vector<A>,compare> stack;
	int min_high = 100000;
	int max_high = 0;
	for (int i = 0; i < map_size; i++) {
		for (int j = 0; j < map_size; j++) {
			cin >> map[i][j];
			stack.push({ map[i][j],i,j });
			if (min_high > map[i][j])
				min_high = map[i][j];
			if (max_high < map[i][j])
				max_high = map[i][j];
		}
	}
	int high = min_high;
	int max_count = 1;
	while (!stack.empty()) {
		int h = stack.top().high;
		int i = stack.top().i;
		int j = stack.top().j;
		if (map[i][j] <= min_high) {
			map[i][j] = 0;
		}
		else {
			int m[110][110] = { 0 };
			for (int i = 0; i < map_size; i++) {
				for (int j = 0; j < map_size; j++) {
					m[i][j] = map[i][j];
				}
			}
			priority_queue<A, vector<A>, compare>  k = stack;
			int count = 0;
			while (!k.empty()) {
				int ii = k.top().i;
				int jj =k.top().j;
				k.pop();
				if (m[ii][jj] != 0) {
					count++;
					dfs(ii, jj, m);
				}
			}
			if (max_count < count)
				max_count = count;
			min_high = map[i][j];
			map[i][j] = 0;

		}
		stack.pop();
	}
	cout << max_count;


	return 0;
}

 

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

2468번: 안전 영역