백준 2573번 : 빙산 c++

코드

#include <iostream>
#include <queue>

using namespace std;

int N, M;
int map[301][301];
bool visit[301][301];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void melt(){
	int temp[301][301];
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			temp[i][j] = map[i][j];
		}
	}
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			if(map[i][j] != 0){
				int minusmelt = 0;
				for(int k = 0; k < 4; k++){
					int mdx = i + dx[k];
					int mdy = j + dy[k];
					if(temp[mdx][mdy] == 0) minusmelt++;
				}
				if(map[i][j] - minusmelt < 0) map[i][j] = 0;
				else map[i][j] = map[i][j] - minusmelt;
			}
		}
	}
}


void bfs(int x, int y){
	queue<pair<int, int> > q;
	q.push(make_pair(x, y));
	visit[x][y] = true;
	
	while(!q.empty()){
		int a = q.front().first;
		int b = q.front().second;
		q.pop();
		for(int i = 0; i < 4; i++){
			int adx = a+dx[i];
			int bdy = b+dy[i];
			if(adx >=0 && adx < N && bdy >=0 && bdy < M){
				if(visit[adx][bdy] == false && map[adx][bdy] != 0){
					visit[adx][bdy] = true;
					q.push(make_pair(adx, bdy));
				}
			}
		}		
	}
}

int main(){
	
	cin >> N >> M;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			cin >> map[i][j];
		}
	}

	
	int x, y;
	int ans = 0;
	bool sep = false;
	
	while(!sep){
		int chk = 0;
			
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				visit[i][j] = false;
			}
		}
		
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				if(map[i][j] != 0){
					chk++;
				}
			}
		}
		if(chk == 1 || chk == 0){
			sep = true;
			ans = 0;
			goto point1;
		}
		
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				if(map[i][j] != 0){
					x = i;
					y = j;
					goto point;
				}
			}
		}
		
	point:
		bfs(x, y);
		
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				if(map[i][j] != 0 && visit[i][j] == false){
					sep = true;
					goto point1;
				}
			}
		}
		
		if(!sep){
			melt();
			ans++;
		}
		
	point1:
		continue;
	}
	
	cout << ans;
	return 0;
}

알게된점.

break는 포문을 하나밖에 못나와서 goto문장을 이용해 이중포문을 빠져나와야 합니다.

빙산이 계속 하나만 남는 경우 0을 출력해야 하는 점을 놓쳐 오래풀었네요.

 

0이아닌 점을 찾아서 bfs나 dfs를 돌고 

visit를 안했는데 0이 아닌 점이 있으면 두개로 분리된거라고 생각하고

이렇게 알고리즘짜니까 되네요.

맞추니까 짜릿하네요ㅋㅋ