2573번 빙산

#pragma warning(disable:4996)
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
#include <random>
#include<time.h>
#include<string>
#include<queue>
#include <set>
#include <map>
#include <list>
#include<stack>
#include<deque>
#include<cstring>
#define ll  long long
#define INF 987654321
#define pa pair<int, int>
using namespace std;
int n, m;
vector<vector<int>>mapp;
int dirX[] = { 1,0 ,-1,0 };
int dirY[] = { 0,1,0,-1 };



int day = 0;

void dfs() {
    vector<vector<bool>> visited;

    visited = vector<vector<bool>>(n, vector<bool>(m, false));
    int island = 0;
    bool flag = false;
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < m; x++) {
            if (mapp[y][x] > 0 && !visited[y][x]) {
                //만약 방문 안한 섬이 있는 경우, queue에 넣고 해당하는 영역을 방문할 수 있도록 진행.
                queue<pa> q;
                visited[y][x] = true;
                q.push({ y,x });
                while (true) {
                    if (q.empty())break;
                    pa cur = q.front(); q.pop();
                    int meltCounter = 0;
                    for (int dir = 0; dir < 4; dir++) {
                        int nextY = cur.first + dirY[dir];
                        int nextX = cur.second + dirX[dir];
                        if (nextY < 0 || nextX < 0 || nextY >= n || nextX >= m || visited[nextY][nextX])
                            continue;
                        if (mapp[nextY][nextX] > 0) {
                            visited[nextY][nextX] = true;
                            q.push({ nextY, nextX });
                        }
                        if (mapp[nextY][nextX] == 0)
                            meltCounter += 1;
                    }
                    mapp[cur.first][cur.second] -= meltCounter;
                    if (mapp[cur.first][cur.second] < 0)mapp[cur.first][cur.second] = 0;
                }
                island++;
            }
        }
    }




    if (island == 1) {
        day += 1;
        dfs();//섬이 1개보다 더 적을 경우, 날짜를 늘려주고 dfs 다시 호출
    }
    else if (day > 0 && island == 0) {
        day = 0;
    }

}


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;

    mapp = vector<vector<int>>(n, vector<int>(m));

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> mapp[i][j];
    dfs();
    cout << day << endl;






    return 0;
}

 

 

1. 문제를 똑바로 읽지 않아 녹는 조건을 제대로 문제에 반영하지 않은 탓

2. bfs를 진행할 때에는, queue에 조건만족 점을 넣을 때 방문 표시를 진행하지 않으면 수많은 점들이 중복해서 queue에 들어와 중복체크를 진행하게 된다는 점.