[백준 2573] 빙산 (C++)

문제 링크: https://www.acmicpc.net/problem/2573

2573번: 빙산

1. 주의할 점

- 반복문을 언제 끝내야 하는지 확실히 한다

- 불필요한 부분을 큐, 벡터에 넣지 않는다

 

2. 구현

- 배열을 입력 받을 때, 빙산인 곳의 좌표를 벡터에 넣는다

- While문을 실행하는데 실행 순서는 다음과 같다

  1) Result++

  2) 빙산을 녹인다

  3) Arr배열 갱신(빙산 중 한 부분을 기억해놓는다 -> 시간단축)

  4) 남은 빙산이 있는가? -> 없으면 빙산전체가 한번에 녹았다는 얘기이므로, Result = 0과 함께 종료

  5) 녹은 빙산을 제외하고 남은 빙산을 가지도록 벡터 갱신

  6) 3번에서 구한 빙산의 부분을 큐에 넣고 BFS탐색을 한다. 큐를 통해 구한 빙산의 크기와 5번에서 갱신한 벡터의 크기가 같지 않다 -> 빙산이 2구역 이상으로 나뉘어졌다

 

3번에서 구한 빙산의 일부를 통해 6번에서 Arr배열 전체를 확인할 필요가 없다.

 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
struct info {
	int x, y, val;
};
info tmp;
int row, col, result = 0;
int arr[300][300];

int main() {
	cin >> row >> col;
	vector<info> ice;
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++) {
			cin >> arr[i][j];
			if (arr[i][j] != 0) {
				tmp.x = j;
				tmp.y = i;
				tmp.val = arr[i][j];
				ice.push_back(tmp);
			}	
		}
	while (1) {
		result++;
		vector<info> dup;
		//빙산을 녹인다
		int len = ice.size();
		for(int k=0;k<len;k++){
			int cx = ice[k].x;
			int cy = ice[k].y;
			for (int i = 0; i < 4; i++) {
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				if (nx >= 0 && ny >= 0 && nx < col & ny < row && arr[ny][nx] == 0) {
					ice[k].val--;
					if (ice[k].val == 0) 
						break;					
				}
			}
		}
		int sx = -1, sy = -1;
		for (int k = 0; k < len; k++) {
			arr[ice[k].y][ice[k].x] = ice[k].val;
			if (ice[k].val != 0) {
				tmp.x = ice[k].x;
				tmp.y = ice[k].y;
				tmp.val = ice[k].val;
				dup.push_back(tmp);
				if (sx == -1 && sy == -1) {
					sx = tmp.x;
					sy = tmp.y;
				}
			}
		}
		if (dup.empty()) {		//남은 빙산이 있는가
			result = 0;
			break;		
		}
		ice.clear();
		ice = dup;
		bool check[300][300] = { false, };
		queue<info> q;
		tmp.x = sx;
		tmp.y = sy;
		q.push(tmp);
		int cnt = 1;
		check[sy][sx] = true;
		while (!q.empty()) {
			int cx = q.front().x;
			int cy = q.front().y;
			q.pop();
			for (int k = 0; k < 4; k++) {
				int nx = cx + dx[k];
				int ny = cy + dy[k];
				if (nx >= 0 && ny >= 0 && nx < col & ny < row && arr[ny][nx]>0 && !check[ny][nx]) {
					check[ny][nx] = true;
					tmp.x = nx;
					tmp.y = ny;
					q.push(tmp);
					cnt++;
				}
			}
		}
		if (cnt!=ice.size()) break;		//빙산이 2구역 이상으로 나눠진 경우
	}
	cout << result;
	system("pause");
	return 0;
}