백준2573 - 빙산

https://www.acmicpc.net/problem/2573

2573번: 빙산

bfs를 이용하여 푼 문제다. 우선 좌표를 입력받아서 빙산의 갯수를 센다. bfs를 실행하였을 때 빙산의 갯수만큼 방문하였다면 빙하가 연결되어 있는 것이고 그렇지 않다면 빙하가 분리되는 원리로 풀었다. 빙하가 녹게하기 위하여 빙하의 위치에서 4방향으로 바다의 위치를 찾아서 저장하고 바다의 위치만큼 빙하의 높이에서 뺀다. 다른 빙하와 연결되어 있는지 다시 찾아서 탐색을 진행하였다. 그리고 저장했던 빙하의 위치를 이용하여 빙하의 높이를 세로 설정한다. 마지막으로 빙하가 분리되는데 걸린 시간을 출력하면 된다. 빙하가 분리되지 않은채 녹는다면 0을 출력하면 된다.

#include <iostream>
#include <queue>
#include <string.h>
#define MAX 301
using namespace std;

int n, m; //세로 n, 가로 m
int all = 0; //총 빙산의 갯수
int mat[MAX][MAX]; //좌표 정보
bool visit[MAX][MAX]; //방문 여부
int turn = 0; //빙하가 녹는 시간

//상하좌우
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

//(x, y)에서 빙산의 높이 z
class Point {
public:
	int x, y, z;
	Point(int x, int y, int z) {
		this->x = x;
		this->y = y;
		this->z = z;
	}
};

//동서남북으로 물을 찾는 함수, 물의 갯수를 반환
int find_water(int x, int y) {
	int water = 0;

	if (1 <= x - 1 && x - 1 <= n && 1 <= y && y <= m && mat[x - 1][y] == 0) {
		water++;
	}
	if (1 <= x + 1 && x + 1 <= n && 1 <= y && y <= m && mat[x + 1][y] == 0) {
		water++;
	}
	if (1 <= x && x <= n && 1 <= y - 1 && y - 1 <= m && mat[x][y - 1] == 0) {
		water++;
	}
	if (1 <= x && x <= n && 1 <= y + 1 && y + 1 <= m && mat[x][y + 1] == 0) {
		water++;
	}

	return water;
}

//빙하를 녹이는 함수
bool bfs(int x, int y) {
	int cnt = all; //총 빙하의 갯수
	queue<pair<int, int>> q; //녹기 전 빙하의 위치
	queue<Point> ice; //해당 시간의 녹는 빙하의 위치

	//처음 위치를 녹기 전 빙하의 위치에 넣고 방문 처리
	q.push(pair<int, int>(x, y));
	visit[x][y] = true;

	while(!q.empty()) {
		cnt--; //빙하의 갯수를 한 개 줄인다.

		//처음 원소를 추출하고 삭제
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		//물을 찾는다. 물의 갯수가 빙하의 높이보다 많으면 그 위치는 0으로 넣는다. 그 외에는 빙하의 높이와 물의 갯수를 빼서 저장
		int water = find_water(x, y);
		if (water > mat[x][y]) {
			ice.push(Point(x, y, 0));
		}
		else {
			ice.push(Point(x, y, mat[x][y] - water));
		}

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (1 <= nx && nx <= n && 1 <= ny && ny <= m && !visit[nx][ny] && mat[nx][ny] != 0) { //유효범위이고 방문한 곳이 아니고 빙하이면 
				q.push(pair<int, int>(nx, ny)); //큐에 삽입
				visit[nx][ny] = true; //방문 처리
			}
		}
	}

	//빙하를 녹게 만든다.
	while (!ice.empty()) {
		int x = ice.front().x;
		int y = ice.front().y;
		int z = ice.front().z;
		ice.pop();

		mat[x][y] = z;
	}

	all = 0; //남은 빙하의 갯수를 세기 위하여 다시 0으로 초기화

	//좌표 정보를 돌면서 빙하면 갯수를 센다.
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (mat[i][j] != 0) {
				all++;
			}
		}
	}

	if (cnt == 0) { //모든 빙하가 연결되어 있어서 모두 한 번씩 방문하였다면 
		return true;
	}
	else { //빙하의 연결이 끊어진 경우
		return false;
	}
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> mat[i][j];
			if (mat[i][j] != 0) { //빙하이면
				all++; //빙하의 갯수 증가
			}
		}
	}

	while (1) {
		bool check = true;
		if (all == 0) { //남은 빙하가 없으면
			cout << 0; //0 출력하고
			return 0; //종료
		}
		for (int i = 1; i <= n; i++) {
			int go = true; //빙하를 찾았는지 못 찾았는지 여부
			for (int j = 1; j <= m; j++) {
				if (mat[i][j] != 0) { //빙하를 찾았다면
					go = false; //빙하를 찾았다고 하고
					memset(visit, false, sizeof(visit)); //모든 좌표 정보를 미방문처리하고
					check = bfs(i, j); //빙하 녹이기 시작
					break; //탈출
				}
			}
			if (!check) { //빙하가 분리되었다면
				cout << turn; //현재까지 시간 출력하고
				return 0; //종료
			}
			if (go == false) { //빙하를 찾았다면
				break; //현재 탐색을 종료
			}
		}
		turn++; //시간을 증가
	}
}