글 읽기 - c++ 안전영역 문제 도저히 틀린 부분을 찾지 못해 올립니다ㅠㅠ

alyssa1996 4년 전 0

질문게시판에 있는 반례(비가 안오는 경우 등)을 다 읽어보고 통과하는 것도 확인했는데, 계속 틀렸다고 나옵니다ㅠㅠ

도와주세요 부탁드립니다!!!

짧게 덧붙이자면, dfs 알고리즘을 이용해 풀었습니다.

change 함수는 비에 잠기는 높이에 해당하는 check배열의 부분을 1로 바꾸는 역할을 합니다.

ok 함수는 접근 가능한지 확인하는 역할을 합니다.

dfs 함수 안에서 인접한 지역이 접근 가능할 경우 다시 dfs를 호출하고, 접근한 지역이 이미 갔었던 지역일 경우 return합니다. 그리고 무조건 접근하면 check배열의 해당 값을 1로 바꿉니다.

메인 함수에서는 arr배열에 주어진 배열값을 입력하고, num이라는 벡터에 주어진 배열값의 값들을 집어 넣습니다(단, 중복되는 수들은 집어넣지 않습니다)

num을 정렬한 후, 작은 높이부터 차근 차근 빗물에 잠기도록 수행하며 안전영역을 구합니다.

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

const int N = 105;
int number, each;
int arr[N][N];
int check[N][N];
int dict[2] = { -1,1 };
vector<int> num;
int result=1;

void change(int a) {
	for (int i = 0; i < number; i++) {
		for (int j = 0; j < number; j++) {
			if (arr[i][j] <= a)
				check[i][j] = 1;
		}
	}
}

bool ok(int x) {//
	if (x > -1 && x < number) return true;
	else return false;
}

void dfs(int i, int j) {
	if (check[i][j] == 1)
		return;
	check[i][j] = 1;
	for (int k = 0; k < 2; k++) {
		if (ok(i + dict[k])) {
			dfs(i + dict[k], j);
		}
	}
	for (int k = 0; k < 2; k++) {
		if (ok(j + dict[k]))
			dfs(i, j + dict[k]);
	}
}


int main(void) {
	cin >> number;
	for (int i = 0; i < number; i++) {
		for (int j = 0; j < number; j++) {
			cin >> each;
			if (!(find(num.begin(), num.end(), each) != num.end()))
				num.push_back(each);
			arr[i][j] = each;
			check[i][j] = 0;
		}
	}

	sort(num.begin(), num.end());

	for (int i = 0; i < num.size(); i++) {
		int cnt = 0;
		change(num[i]);
		for (int a = 0; a < number; a++) {
			for (int b = 0; b < number; b++) {
				if (check[a][b]==1)
					continue;
				dfs(a, b);
				cnt++;
			}
		}
		if (result <= cnt)
			result = cnt;
		else break;
		for (int a = 0; a < number; a++) {
			for (int b = 0; b < number; b++) {
				check[a][b] = 0;
			}
		}
	}
	cout << result;
	 
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.