글 읽기 - 어디서 틀린건지 잘 모르겠습니다. 제가 생각한 알고리즘 적어 놓았습니다.

alsghdjrk 5년 전 0

맵의 크기와 비의 량을 받는다
받는 비의 량을 sort 내림차순으로 돌려 가장 많은 비가 나렸을 떄를 받는다.
함수 bfs로 넘어간다 인자에는 가장 많은 비의량과 맵의 사이즈가 넘어간다

bfs(비의 최대량, 맵의크기)

인자로 비의 량, safezone(temp), 백터가 있고 백터는 safezone의 갯수를 집어넣을 것이다.
while문을 반복한다 최대비의량 부터 0 까지
임시맵의 생성 임시맵은 비보다 작은곳은 0 비와 같거나 큰 곳은 1로 놓여진다
1인 지역을 방문하면 함수 bfs1를 실행 bfs1은 방문한 곳을 0으로 그리고 상하좌우 방문
벡터SZ에 safezone의 갯수 저장
while 문이 끝나면 sort를 이용해 벡터SZ를 내림차순 정렬
return 벡터SZ[0] == 가장큰값

이렇게 프로그램을 짜서 돌렸습니다.

테스트 케이스는 잘돌아갑니다. 알고리즘 부분에서 틀린 것 지적해 주세요;;

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

int map[100][100];
int tempmap[100][100];

vector<int> maxrain;
bool myfuction(int a, int b){
	return a>b;
}

void bfs1(int x, int y){
	if(tempmap[x][y] ==1){

		tempmap[x][y] =0;
		bfs1(x+1,y);
		bfs1(x-1,y);
		bfs1(x,y+1);
		bfs1(x,y-1);
	}
	else return;

}

int bfs(int maxrain,int mapsize){
	int rain = maxrain;
	int safezone =0;
	vector<int> SZ;
	while(rain >=0){
		safezone =0;
		//cout<< rain<<"\n";
		rain--;
		for(int i=0;i<mapsize;i++){
			for(int j=0;j<mapsize;j++){
				if (map[i][j] <= rain){
					tempmap[i][j] = 0;// 작으면 0;
				}
				else tempmap[i][j] =1; // 물보다 높으면 1
			}
		}


		// for(int i=0;i<mapsize;i++){
		// 	for(int j=0;j<mapsize;j++){
		// 		cout<< tempmap[i][j];
		// 	}
		// 	cout<<"\n";
		// }// 맵이 들어오는거 확인



		for(int x=0;x<mapsize;x++){
			for(int y=0;y<mapsize;y++){
				if(tempmap[x][y] == 1){
					safezone +=1;
					bfs1(x,y);
				}

			}
		}

		SZ.push_back(safezone);
	}
	sort(SZ.begin(),SZ.end(),myfuction);
	return SZ[0];
}



int main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++){
	if(tempmap)	for(int j=0;j<n;j++){
			cin>>map[i][j];
			maxrain.push_back(map[i][j]);
		}
	}
	sort(maxrain.begin(),maxrain.end(),myfuction);// 오름차순 정렬
	cout<< bfs(maxrain[0],n);	
}

//안전지역의 갯수를 출력하라
//안전지역은 4개의 면에 만 해당된다
//물의량은 0 부터 최대 보다 낮은 갯수가 들어오는대
// 어차피 최대지역이 잠기면 다 잠긴다고 보면된다

alsghdjrk 5년 전 0

제가 쓰고 제가 답들 답니다.

map을 한번 패딩하고 실행 하니까 답이 잘 나옵니다.

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

문제

문제

출처

ICPC

어디서 틀린건지 잘 모르겠습니다. 제가 생각한 알고리즘 적어 놓았습니다.

alsghdjrk 5년 전 0

alsghdjrk 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말