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

1. 조건

- 바다 = 0 / 빙산 > 0

- 동서남북에 붙어있는 바다 갯수만큼 줄어듦

- 0보다 더 줄어들지는 않음

 

2. 입력

- 가로 m, 세로 n

- 첫번째 행과 열, 마지막 행과 열은 항상 0 => 범위 체크 하지 않아도 된다.

 

3. 출력

- 두덩이 이상 분리되는데 걸리는 최소시간

- 분리되지 않으면 0 출력

 

4. 경계값 반례

4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0
// 0

3 3
0 0 0
0 1 0
0 0 0
// 0

6 7
0 0 0 0 0 0 0
0 5 0 6 0 2 0
0 3 0 7 0 1 0
0 2 4 8 0 4 0
0 0 0 0 0 2 0
0 0 0 0 0 0 0
// 1

 

5. 풀이

(1) 빙산의 부분별 줄어들 높이를 구한다.

ㄴ 높이 계산과 동시에 결과값을 반영해버리면 옆에 있는 부분이 녹을 높이를 구할 때 영향이 가기 때문에 바로 반영하지는 않는다.

(2) 구한 높이를 반영해 빙산의 새로운 높이를 구한다.

ㄴ 0보다 작아질 수 없으므로 음수가 될 경우에는 0으로 처리

(3) 탐색을 통해 빙산이 몇 덩이인지 구한다.

 

---

 

C++)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define MAX_NUM 302
using namespace std;

int arr[MAX_NUM][MAX_NUM];
bool visited[MAX_NUM][MAX_NUM];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int n, m;

queue<pair<int, int>> q;				// 빙산 부분 별 위치
vector<pair<pair<int, int>, int >> v;	// 빙산 부분 별 녹을 높이

int CheckCount() {
	int cnt = 0;
	queue<pair<int, int>> temp;


	for (auto ele : v) {
		int x = ele.first.first;
		int y = ele.first.second;

		// 녹을 부분이 있고 아직 방문 안했다 -> 시작점이다
		if (arr[x][y] > 0 && !visited[x][y]) {
			visited[x][y] = true;
			temp.push({ x,y });
			cnt++;

			while (!temp.empty()) {
				int cx = temp.front().first;
				int cy = temp.front().second;
				temp.pop();

				for (int k = 0; k < 4; k++) {
					int nx = cx + dx[k];
					int ny = cy + dy[k];

					if (arr[nx][ny] > 0 && !visited[nx][ny]) {
						visited[nx][ny] = true;
						temp.push({ nx,ny });
					}
				}
			}
		}
	}

	return cnt;
}

void MeltDown() {
	for (auto ele : v) {
		int x = ele.first.first;
		int y = ele.first.second;
		int meltingSize = ele.second;

		if (arr[x][y] - meltingSize > 0) {
			arr[x][y] -= meltingSize;
			
			// 아직 녹을 수 있다면 큐에 다시 넣어주기
			q.push({ x,y });
		}
		else
			arr[x][y] = 0;
	}
}

int CheckIceMeltingSize() {
	while(!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		int cnt = 0;

		// 상하좌우 빙하 녹을 면 계산
		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];

			if (arr[nx][ny] == 0)
				cnt++;
		}

		// 내부에 있는 빙산 (바다물과 닿지 않아 영향이 없는 빙산)도 넣어줘야함
		v.push_back({ {x,y},cnt });
	}

	// 녹여본다
	MeltDown();

	// 몇덩이인지 계산한다
	return CheckCount();
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];

			if (arr[i][j] > 0)
				q.push({ i,j });
		}
	}

	int ans = 0;
	
	// 큐가 비어있지 않다. -> 녹을 빙산이 있다
	while (!q.empty()) {
		if (CheckIceMeltingSize() >= 2)
			break;
		
		ans++;

		// 초기화
		for (int i = 0; i < n; i++)
			fill(visited[i], visited[i] + m, false);
		v.clear();
	}

	(q.empty()) ? cout << 0 : cout << ans + 1;

	return 0;
}

 

 

 

Python)

# 2206
import sys
from collections import deque

read = sys.stdin.readline

dx = [1,0,-1,0]
dy = [0,1,0,-1]
q = deque()

n, m = map(int, read().rstrip().split())

ice = [[] * m for _ in range(n)]
visited = [[False] * m for _ in range(n)]
ice_melting_size = []

for i in range(n):
    ice[i] = list(map(int, read().rstrip().split()))

    for j in range(m):
        if ice[i][j]:
            q.append((i,j))

def CheckCount():
    temp = deque()
    cnt = 0

    for ele in ice_melting_size:
        x, y, melt = ele
        
        if ice[x][y] and not visited[x][y]:
            visited[x][y] = True
            temp.append((x,y))
            cnt += 1

            while temp:
                cx, cy = temp.popleft()

                for k in range(4):
                    nx = cx + dx[k]
                    ny = cy + dy[k]

                    if ice[nx][ny] and not visited[nx][ny]:
                        visited[nx][ny] = True
                        temp.append((nx,ny))

    return cnt


def Melting():
    for ele in ice_melting_size:
        x, y, melting_size = ele
        ice[x][y] = max(0, ice[x][y] - melting_size)
        
        if ice[x][y]:
            q.append((x,y))


def CheckMeltingSize():
    while q:
        x, y = q.popleft()
        cnt = 0

        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]

            if ice[nx][ny] == 0:
                cnt += 1

        ice_melting_size.append((x,y,cnt))

    Melting()
    return CheckCount()

ans = 0

while q:
    if CheckMeltingSize() >= 2:
        break

    ans += 1
    visited = [[False] * m for _ in range(n)]
    ice_melting_size = []

print(ans + 1 if q else 0)