백준 그래프 추천문제인 빙산 문제를 풀어봤다. 문제 자체는 꽤 쉬운데 쉽게 실수를 할 수 있을법한 문제다. 그래도 솔직히 이런 시뮬레이션이 섞인 BFS 문제를 백준에서 많이 풀어봐서 그런지 문제를 읽자마자 어떻게 풀어야할지 감이 왔고. 코드를 다 만든 후 에도 다시 읽어보면서 실수가 나올 부분에서 모두 에러체킹을 머리속에서 해주었다.
확실히 이 전에 있었던 힘든 경험들이 이런 시뮬레이션 타입 문제에 더 강점을 부여해준거같아서 기분이 좋다.
실수를 할만했던 코드 중에는 뭉친 빙산을 확인 해줄때랑 빙산을 녹이는 과정인데. 이 둘의 순서를 잘 생각하면서 해줘야지 문제없이 테스트가 통과했을거다. 예전에 아기 상어 문제들을 풀때가 좀 생각이 났고 같은 실수는 하지않아서 다행이다.
#include <iostream>
#include <bits/stdc++.h>
#define endl "\n"
#define MAX 100010
using namespace std;
int N,M;
int matrix[301][301];
int ocean[301][301];
bool visited[301][301];
vector<pair<int,int>> dir = {{0,1},{0,-1},{1,0},{-1,0}};
void Input(){
cin >> N >> M;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> matrix[i][j];
}
}
}
void bfs(int x, int y){
queue<pair<int,int>> q;
q.push({x,y});
visited[x][y] = true;
while(!q.empty()){
int size = q.size();
for(int i = 0; i < size; i++){
pair<int,int> first = q.front();
q.pop();
int xx = first.first, yy = first.second;
for(pair<int,int>& p : dir){
int nX = xx + p.first;
int nY = yy + p.second;
if(nX < 0 || nY < 0 || nX >= N || nY >= M || visited[nX][nY] || matrix[nX][nY] <= 0) continue;
q.push({nX,nY});
visited[nX][nY] = true;
}
}
}
}
void melt(int i, int j){
int oceanCnt = 0;
for(pair<int,int>& p : dir){
int nX = i + p.first;
int nY = j + p.second;
if(nX < 0 || nY < 0 || nX >= N || nY >= M || matrix[nX][nY] != 0) continue;
if(matrix[nX][nY] == 0) oceanCnt++;
}
ocean[i][j] = oceanCnt;
}
void Solution(){
int year = 0, cnt = 0;
bool exist = false;
while(1){
memset(visited,false,sizeof(visited));
memset(ocean,0,sizeof(ocean));
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
if(matrix[i][j] > 0){
exist = true;
if(!visited[i][j]){
cnt++;
bfs(i,j);
}
melt(i,j);
}
}
}
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
if(ocean[i][j] > matrix[i][j]) matrix[i][j] = 0;
else matrix[i][j] -= ocean[i][j];
}
}
if(cnt >= 2){
cout << year;
return;
}
if(!exist) break;
exist = false;
cnt = 0;
year++;
}
cout << 0;
}
void Solve(){
Input();
Solution();
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("input.txt", "r", stdin);
Solve();
return 0;
}
배운점:
1. visited 배열 활용
2. BFS 의 활용