글 읽기 - 반례가 더이상 없는것 같습니다

swinnovator 2년 전 0

https://www.acmicpc.net/board/...

여기있는 테스트케이스를 모두 통과했는데도 6%에서 틀렸습니다가 떠요

생각한 방법은

1. 입력을 받으면서 최대높이와, 빙산의 위치를 vector에 저장한다

2. BFS를 이용해 그룹의 개수를 파악한다.

3. 그룹이 2개이상으로 쪼개지면 몇년이 지났는지를 출력하고 프로그램을 종료한다.

4. 그룹이 2개 이상으로 쪼개지지 않으면 adjacentAir 에 주변의 바다개수를 저장하고 한꺼번에 녹인다.

5.빙산의 최대 높이 만큼 반복한다.

6. 반복이 모두 끝났는데도 분리가 2조각 이상으로 분리되지 않을시에 0을 출력한다.

입니다.

혹시라도 제가 생각하지 못한부분 지적해주시면 감사드리겠습니다

//#define TEST

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

int arr[300][300];
int isVisited[300][300];
int x_size, y_size;
void PrintArray();
void InitIsVisited();
bool isAlreadyDivided();
void BFS(int fromX, int fromY, int group);
void Melt(const vector<pair<int,int>> &icePosition);

int main(){
	#ifdef TEST
	freopen("input9.txt", "r", stdin);
	#endif

	vector<pair<int,int>> icePosition;
	int maxHeight = 0;

	cin >> y_size >> x_size;
	for(int y = 0; y < y_size; y++){
		for(int x = 0; x < x_size ;x++){
			cin >> arr[y][x];
			maxHeight = arr[y][x] > maxHeight ? arr[y][x] : maxHeight;
			if(arr[y][x] != 0){
				icePosition.push_back(make_pair(y, x));
			}
		}
	}

	//solve
	int year = 0;

	for(int h = 0; h < maxHeight; h++){
		int group = 0;
		for(int y = 0; y < y_size; y++){
			for(int x = 0; x < x_size; x++){
				if(arr[y][x] != 0 && isVisited[y][x] == 0){
					BFS(x,y,++group);
				}
			}
		}

		if(group >= 2){
			cout << year << '\n';
			return 0;
		}
		Melt(icePosition);
		InitIsVisited();
		year++;
	}

	cout << 0 << '\n';


	#ifdef TEST
	fclose(stdin);
	#endif

	return 0;
}

void PrintArray(){
	cout << '\n';
	for(int y = 0; y < y_size; y++){
		for(int x = 0 ; x < x_size ;x++){
			cout << arr[y][x] << ' ';
		}
		cout << '\n';
	}
}

void InitIsVisited(){
	for(int y = 0 ; y < y_size; y++){
		for(int x = 0; x < x_size; x++){
			isVisited[y][x] = 0;
		}
	}
}

void Melt(const vector<pair<int,int>> &icePosition){
	const int dx[] = { 1,-1,0,0 };
	const int dy[] = { 0,0,1,-1 };
	vector<int> adjacentAir;

	for(pair<int,int> p : icePosition){
		int x = p.second;
		int y = p.first;
		int adjAir = 0;

		for(int dir = 0; dir < 4; dir++){
			int X = x + dx[dir];
			int Y = y + dy[dir];

			if((0 <= X && X < x_size) && (0 <= Y && Y < y_size)){ //is inside range
				if(arr[Y][X] == 0) { //is Air
					adjAir++;
				}
			}
		}
		adjacentAir.push_back(adjAir);
	}

	//melt
	for(int idx = 0; idx < icePosition.size(); idx++){
		int x = icePosition[idx].second;
		int y = icePosition[idx].first;

		if(arr[y][x] - adjacentAir[idx] <= 0){
			arr[y][x] = 0;
		}
		else{
			arr[y][x] -= adjacentAir[idx];
		}
	}
}

void BFS(int fromX, int fromY, int group) {
	const int dx[] = { 1,-1,0,0 };
	const int dy[] = { 0,0,1,-1 };
	queue<pair<int,int>> bfs;

	bfs.push(make_pair(fromY,fromX));
	isVisited[fromY][fromX] = group;

	while(!bfs.empty()){
		int x = bfs.front().second;
		int y = bfs.front().first;
		for(int dir = 0; dir < 4; dir++){
			int X = x + dx[dir];
			int Y = y + dy[dir];
			if((0 <= X && X < x_size) && (0 <= Y && Y < y_size)){
				if(isVisited[Y][X] == 0 && arr[Y][X] != 0){
					isVisited[Y][X] = group;
					bfs.push(make_pair(Y,X));
				}
			}
		}
		bfs.pop();
	}
}

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

문제

문제

출처

ICPC

반례가 더이상 없는것 같습니다

swinnovator 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말