(BOJ) 2573 빙산

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

문제풀이:

1. 입력 받을 때 빙산이 있는 부분을 q에 넣는다.  -> arr배열에 저장

2. q를 전부 보면서 주변에 바다의 개수를 세서 _minus라는 queue에 넣음

3. _minus에 넣은 만큼 arr배열에 적용

4. q에 들어있는 임의의 점에서 bfs를 돌렸을 때 모든 빙산에 갈 수 있으면 한덩어리

2->3->4->2 반복하다

check()==true이거나 q가 empty이면 끝 

소스코드:

#include <iostream> #include <vector> #include <map> #include <queue> #include <string> #include <string.h> #include <algorithm> using namespace std; int n, m, arr[301][301],cnt; int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,-1,0,1 }; bool visit[301][301]; queue<pair<int, pair<int, int>>> _minus; queue<pair<int, int>> q; void func() { int len = q.size(); for (int i = 0; i < len; i++) { int x = q.front().first; int y = q.front().second; q.pop(); int t = 0; for (int j = 0; j < 4; j++) { if (arr[x + dx[j]][y + dy[j]] <= 0) t++; } if (arr[x][y] - t > 0) q.push({ x,y }); _minus.push({ t,{x,y} }); } } void sea() { while (!_minus.empty()) { arr[_minus.front().second.first][_minus.front().second.second] -= _minus.front().first; _minus.pop(); } } bool check() { memset(visit, false, sizeof(visit)); queue<pair<int, int>> cur; cur.push({ q.front().first,q.front().second }); int t = 0; while (!cur.empty()) { int x = cur.front().first; int y = cur.front().second; cur.pop(); for (int i = 0; i < 4; i++) { if (arr[x + dx[i]][y + dy[i]] <= 0 ||visit[x + dx[i]][y + dy[i]]) continue; visit[x + dx[i]][y + dy[i]] = true; cur.push({ x + dx[i],y + dy[i] }); t++; } } if (t == q.size()) return false;   // 한 덩어리 return true; } int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); 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 }); } } while (!q.empty()) { func(); if (q.empty()) break; sea(); if (check()) { cout << cnt+1 << '\n'; return 0; } cnt++; } cout << "0\n"; return 0; }