[2638번] 치즈

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

이 문제는 BFS의 기본이 되는 문제이며 다음과 같이 해결할 수 있다.

1. 각 모서리에는 치즈가 없다고 명시되어 있으니 0,0부터 시작해서 상,하,좌,우에 치즈가 존재하면 +1을 해주며

0,0 ~ n-1,m-1까지 bfs를 돌린다.

2. bfs가 한번 끝이나면 이중 포문에서 치즈가 공기에 2번이상 맞닿은 부분에 한해 0으로 값을 초기화 해주고

이때 한번이라도 치즈가 녹았다면 day++를 해준다.

3. 단한번도 치즈가 녹지 않았다면 break를 통해 day를 출력하고 프로그램을 종료한다.  

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <memory.h>
 
using namespace std;
 
int arr[102][102];
int dy[4] = { 1, 0, -1, 0 };
int dx[4] = { 0, 1, 0, -1 };
 
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", &arr[i][j]);
 
    int day = 0;
    while (1)
    {
        bool inner[102][102] = { true, };
        bool visit[102][102] = { false, };
        int chk[102][102] = { 0, };
 
        queue<pair<int, int> > q;
 
        q.push({ 0,0 });
 
        while (!q.empty())
        {
            int y = q.front().first;
            int x = q.front().second;
 
            q.pop();
 
            if (visit[y][x])
                continue;
 
            visit[y][x] = true;
            inner[y][x] = false;
 
            for (int i = 0; i < 4; i++)
            {
                int hy = dy[i] + y;
                int hx = dx[i] + x;
 
                if (!((0 <= hy && hy < n) && (0 <= hx && hx < m)))
                    continue;
 
                if (arr[hy][hx] == 1)
                    chk[hy][hx]++;
 
                else if(!visit[hy][hx])
                    q.push({ hy,hx });
            }
        }
 
        bool erase = false;
        for(int i = 0 ; i < n; i ++)
            for (int j = 0; j < m; j++)
            {
                if (chk[i][j] >= 2)
                {
                    arr[i][j] = 0;
                    erase = true;
                }
            }
 
        if (erase)
            day++;
        else
            break;
    }
 
    printf("%d", day);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>