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)'백준 2 > 그래프' 카테고리의 다른 글
| [백준 2146] 다리 만들기 (C++/Python) (0) | 2023.07.05 |
|---|---|
| [백준 13549] 숨바꼭질3 (C++/Python) (0) | 2023.07.04 |
| [백준 7562] 나이트의 이동 (Python) (0) | 2023.06.28 |
| [백준 5014] 스타트링크 (C++/Python) (0) | 2023.04.05 |
| [백준 1926] 그림 (C++/Python) (0) | 2023.03.24 |