[2573번] 빙산

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

2. 시뮬레이션

이 문제는 BFS가 핵심이긴 하지만, 거의 시뮬레이션에 가까운 것 같다.

요구하는 사항이 너무 많은 문제여서 좋으면 좋은 문제라고 할 수 있고, 너무 귀찮으면 귀찮은 문제라 할 수 있을 듯 하다.

빙산을 녹이는 기준은 바다가 있는 곳을 기준으로 사방향에 아직 빙산이 있다면 녹여주고,

그 녹았는 빙산이 0이될 경우 다음 빙산에 영향을 주면 안되기에 visit 배열로 그것을 막아준다.(동시에 모두 녹도록 만들어 준다.)

빙산 그룹을 확인하는 방법은 그냥 bfs를 2중 포문속에서 돌며 그룹을 지어주어 2그룹이 나오는지 확인하면 된다.

정말 알고리즘 측면으로 해석하기에는 별로 할 말이없지만, 코드를 막상 짜면 매우 많은 것을 요구하는 것 같다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <queue>
#include <memory.h>
 
using namespace std;
 
typedef pair<int, int> pii;
int map[302][302];
int ans[302][302];
 
int visit[302][302];
 
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int total;
 
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            scanf("%d", &map[i][j]);
            total += map[i][j];
        }
 
    int cnt = 1;
    int visitCnt = 1;
    int time = 0;
 
    bool finish = false;
 
    // 빙산 그룹 확인(처음부터 2그룹인지)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (map[i][j] && ans[i][j] == 0)
            {
                queue<pii> q;
 
                q.push({ i,j });
 
                while (!q.empty())
                {
                    int y = q.front().first;
                    int x = q.front().second;
 
                    q.pop();
 
                    if (ans[y][x])
                        continue;
 
                    ans[y][x] = cnt;
 
                    for (int k = 0; k < 4; k++)
                    {
                        int hereY = y + dy[k];
                        int hereX = x + dx[k];
 
                        if (hereY >= n || hereY < 0 || hereX >= m || hereX < 0 || !map[hereY][hereX])
                            continue;
 
                        q.push({ hereY, hereX });
                    }
                }
                cnt++;
 
                if (cnt == 3)
                {
                    printf("0");
                    return 0;
                }
            }
    
 
    while (!finish)
    {
        // 처음 빙산 시작 위치 파악
        memset(ans, 0, sizeof(ans));
        cnt = 1;
 
        // 빙산 녹이기
        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++)
                if (map[i][j] == 0 && visit[i][j] != visitCnt)
                {
                    for (int k = 0; k < 4; k++)
                    {
                        int hereI = i + dy[k];
                        int hereJ = j + dx[k];
 
                        if (map[hereI][hereJ])
                        {
                            map[hereI][hereJ]--;
                            visit[hereI][hereJ] = visitCnt;
                            total--;
                        }
                    }
                }
 
        // 빙산이 다녹아버렸으면
        if (total == 0)
        {
            printf("0");
            return 0;
        }
 
        visitCnt++;
 
 
        // 빙산 그룹 확인
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (map[i][j] && ans[i][j] == 0)
                {
                    queue<pii> q;
 
                    q.push({ i,j });
 
                    while (!q.empty())
                    {
                        int y = q.front().first;
                        int x = q.front().second;
 
                        q.pop();
 
                        if (ans[y][x])
                            continue;
 
                        ans[y][x] = cnt;
 
                        for (int k = 0; k < 4; k++)
                        {
                            int hereY = y + dy[k];
                            int hereX = x + dx[k];
 
                            if (hereY >= n || hereY < 0 || hereX >= m || hereX < 0 || !map[hereY][hereX])
                                continue;
 
                            q.push({ hereY, hereX });
                        }
                    }
                    cnt++;
 
                    // 빙산이 2그룹으로 나뉘었다면
                    if (cnt == 3)
                        finish = true;
                }
 
        time++;            
    }
    
    cout << time << endl;
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>