[BOJ] 2573 빙산

www.acmicpc.net/problem/2573

2573번: 빙산

#include<cstdio>
#include<queue>
typedef long long ll;
using namespace std;
int board[305][305];
int board2[305][305];
bool visited[305][305];
int mx[4] = {0,0,1,-1}; //동 서 남 북 
int my[4] = {1,-1,0,0};
int year; 
int solve(int n,int m)
{
	int tx,ty;
	int qx,qy;
	int flag,cnt = 0;
	queue<pair <int, int>> q;
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			board2[i][j] = board[i][j];
			if(!board[i][j] || visited[i][j]) continue;
			visited[i][j] = 1;
			q.push(make_pair(i,j));
			while(!q.empty())
			{
				qx = q.front().first;
				qy = q.front().second;
				q.pop();
				for(int k = 0; k < 4; k++)
				{	
					tx = qx + mx[k];
					ty = qy + my[k];
					if(board[tx][ty] && !visited[tx][ty])
					{
						q.push(make_pair(tx,ty));
						visited[tx][ty] = 1;
					}
				}	
			}
			cnt++;
			
			// 마지막에 1개만 남은경우 
		}
	}
	if(cnt > 1){
		printf("%d\n",year);
		return 1;
	} 
	if(cnt == 0){
		printf("0\n");
		return 0;
	}
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{	
			visited[i][j] = 0;
			if(!board2[i][j]) continue;// board가 0이 될 수 있기때문. 
			for(int k = 0; k < 4; k++)
			{
				tx = i + mx[k];
				ty = j + my[k];
				if(!board2[tx][ty])
				{
					//동서남북이 0 이면
					board[i][j]--;
					if(board[i][j] < 0) board[i][j] = 0;
				}
			}
		}
	}
	year++;
	
	//1년 지남  
	
	return 2;
}

int main(void)
{
	int n,m;
	//n 행 m 열
	scanf("%d %d",&n,&m);
	
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			scanf("%d",&board[i][j]);
		}
	}
	//printf("\n") ;
	while(1){
		if(solve(n,m) != 2)
			break;
	}
	return 0;
}

---

풀이방법 : 완전 탐색으로 1년이 지나는걸 계산, BFS로 덩어리 계산

​

시행착오 :

1. 처음에 그냥 완전탐색 문제인줄..

1.1) 1년이 지날때마다 바뀌는 배열 만들었음.

1.2) 동서남북이 0이면 빙산이 나누어진걸로 계산함. (틀리고 나서 )아래 반례를 생각함.

-> 0 0 0 0 0

0 0 0 1 0

0 0 0 0 0

0 0 0 0 0

1.3) 아래와 같은 반례도 빙산이 2개인데 1.2 방법으로는 찾을 수 없는걸 깨달음.

->0 0 0 0 0

0 1 1 0 0

0 0 0 0 0

01 1 0 0

0 0 0 0 0

​

2. 1,1부터 시작해서 한 점을 따라서 이어져있으면 끝까지 쭉 따라가서 그곳을 방문처리 하고 섬 하나로 만들어버림.

뭔말인지 아시나요?

왼쪽 그림의 1은 그냥 한번에 다 이어지므로 빙산이 1개입니다.

오른쪽 그림의 1 2 3 은 그림이 이어지는걸 연결하면 되므로 섬이 3개입니다.

​

bfs로 하면 그냥 깔끔하게 개수를 구할 수 있었습니다.

​

만약에 탐색을 한번도 못한다면 빙하가 다 녹은거겠죠?

​

==> 빙산이 2개 이상인경우

if(cnt > 1){

printf("%d\n",year);

return 1;

}

​

==> 빙산이 없는경우

if(cnt == 0){

printf("0\n");

return 0;

}

​

​

=====END====