[BaekJoon] 백준 2573번 빙산

 

[BaekJoon] 백준 2573번 빙산

 

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

 

 

내코드

 

- BFS/DFS 문제. 인접한 노드들 개수를 세줘야되서 bfs의 재귀로 푸는건 안됬다. 그래서 익숙한 bfs로 풀어줬다.

- BFS: Queue, 너비우선, push 할때 visited = true;

function bfs(){
	1. pop
	2. 인접한 노드들 push
}

- while문을 돌릴때마다 모든 노드가 0이 되지 않았는지 체크해준다.

- while문 안에서 변수들을 초기화 해준후, bfs를 돌려준다. 이때 인접 노드가 0이면 배열 nearNode[x][y]++을 해줘서 인접한 바다노드의 개수를 세준다.

- 한 뭉텅이가 끝나면 year확인 후 2보다 크지 않으면 세준 인접한 바다노드의 개수만큼 arr에서 빼준다.

- 다시 while문을 돌린다.

 

#include <iostream>
#include <string>
#include <queue>
#include <utility>

using namespace std;

const int MAX = 300;
int n, m;
int arr[MAX][MAX] = { 0, };
bool visited[MAX][MAX] = { false, };
int nearNode[MAX][MAX] = { 0, };
int numIce = 0;
int year = 0;
bool isZero = false;
int dx[] = { 0,1,0,-1 };
int dy[] = { -1,0,1,0 };
queue<pair<int, int>> qu;

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
		}
	}
	while (!isZero) {
		isZero = true;
		numIce = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				visited[i][j] = false;
				nearNode[i][j] = 0;
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (visited[i][j] == true || arr[i][j] == 0) continue;
				qu.push(make_pair(i, j));
				visited[i][j] = true;

				while (!qu.empty()) {
					pair<int, int> cur = qu.front();
					qu.pop();
					for (int i = 0; i < 4; i++) {
						int x = cur.first + dx[i];
						int y = cur.second + dy[i];
						if (x < 0 || y < 0 || x >= n || y >= m) continue;
						if (arr[x][y] == 0) {
							nearNode[cur.first][cur.second]++;
							continue;
						}
						if (visited[x][y] == true) continue;
						qu.push(make_pair(x, y));
						visited[x][y] = true;
					}
				}
				numIce++;
			}
		}
		if (numIce >= 2) {
			cout << year;
			return 0;  
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j] < nearNode[i][j]) arr[i][j] = 0;
				else arr[i][j] -= nearNode[i][j];
			}
		}
		//check if ice all melted
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (arr[i][j] != 0) isZero= false;
			}
		}
		year++;
	}
	cout << 0;
	return 0;
}

 

참고