[백준 2638] 치즈 (BFS) (C/C++) (★★★)

#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
 
int map[110][110];
int visited[110][110];
int row, col;
int time;
 
queue<pair<int, int>> q;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < row && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void paint(int x, int y, int level)
{
    queue<pair<int, int>> c;
    c.push({x, y});
    visited[x][y] = 1;
    
    while(!c.empty())
    {
        int x = c.front().first;
        int y = c.front().second;
        c.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 1 && visited[xpos][ypos] == 0)
            {
                map[xpos][ypos] = level;
                c.push({xpos, ypos});
                visited[xpos][ypos] = 1;
            }
        }
    }
}
 
void init(int x, int y)
{
    int cnt = 0;
    
    for(int k = 0; k < 4; k++)
    {
        int xpos = x+dx[k];
        int ypos = y+dy[k];
        
        if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 2)
        {
            cnt++;
        }
    }
    
    if(cnt >= 2)
    {
        q.push({x, y});
    }
}
 
void melt()
{
    int size = q.size();
    
    while(size--)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        map[x][y] = 2;
    }
}
 
int check()
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 1)
            {
                return 0;
            }
        }
    }
    
    return 1;
}
 
int main(void)
{
//    freopen("B2638_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
        }
    }
    
    // 치즈는 1, 바깥쪽은 2, 안쪽은 3~ 색칠 
    int level = 2;
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 0)
            {
                paint(i, j, level);
                level++;    
            }
        }
    }
    
    while(1)
    {    
        memset(visited, 0, sizeof(visited));
        
        time++;
        
        // 바깥쪽과 2면 이상 접촉하는 치즈, 큐에 삽입 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 1)
                {
                    init(i, j);            
                }
            }
        }
        
        melt();
        
        // 치즈가 녹아서 바깥쪽과 안쪽이 연결되었으면 다시 2로 색칠 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 2 && visited[i][j] == 0)
                {
                    paint(i, j, 2);
                }
            }
        }
        
        if(check() == 1)
        {
            cout << time;
            break;
        }
    }
    
    return 0;
}

#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
 
int map[110][110];
int visited[110][110];
int row, col;
int time;
 
queue<pair<int, int>> q;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < row && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void paint(int x, int y, int level)
{
    queue<pair<int, int>> c;
    c.push({x, y});
    visited[x][y] = 1;
    
    while(!c.empty())
    {
        int x = c.front().first;
        int y = c.front().second;
        c.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 1 && visited[xpos][ypos] == 0)
            {
                map[xpos][ypos] = level;
                c.push({xpos, ypos});
                visited[xpos][ypos] = 1;
            }
        }
    }
}
 
void init(int x, int y)
{
    int cnt = 0;
    
    for(int k = 0; k < 4; k++)
    {
        int xpos = x+dx[k];
        int ypos = y+dy[k];
        
        if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 2)
        {
            cnt++;
        }
    }
    
    if(cnt >= 2)
    {
        q.push({x, y});
    }
}
 
void melt()
{
    int size = q.size();
    
    while(size--)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        map[x][y] = 2;
    }
}
 
int check()
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 1)
            {
                return 0;
            }
        }
    }
    
    return 1;
}
 
int main(void)
{
//    freopen("B2638_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
        }
    }
    
    // 치즈는 1, 바깥쪽은 2, 안쪽은 3~ 색칠 
    int level = 2;
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 0)
            {
                paint(i, j, level);
                level++;    
            }
        }
    }
    
    while(1)
    {    
        memset(visited, 0, sizeof(visited));
        
        time++;
        
        // 바깥쪽과 2면 이상 접촉하는 치즈, 큐에 삽입 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 1)
                {
                    init(i, j);            
                }
            }
        }
        
        melt();
        
        // 치즈가 녹아서 바깥쪽과 안쪽이 연결되었으면 다시 2로 색칠 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 2 && visited[i][j] == 0)
                {
                    paint(i, j, 2);
                }
            }
        }
        
        if(check() == 1)
        {
            cout << time;
            break;
        }
    }
    
    return 0;
}

#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
 
int map[110][110];
int visited[110][110];
int row, col;
int time;
 
queue<pair<int, int>> q;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < row && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void paint(int x, int y, int level)
{
    queue<pair<int, int>> c;
    c.push({x, y});
    visited[x][y] = 1;
    
    while(!c.empty())
    {
        int x = c.front().first;
        int y = c.front().second;
        c.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 1 && visited[xpos][ypos] == 0)
            {
                map[xpos][ypos] = level;
                c.push({xpos, ypos});
                visited[xpos][ypos] = 1;
            }
        }
    }
}
 
void init(int x, int y)
{
    int cnt = 0;
    
    for(int k = 0; k < 4; k++)
    {
        int xpos = x+dx[k];
        int ypos = y+dy[k];
        
        if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 2)
        {
            cnt++;
        }
    }
    
    if(cnt >= 2)
    {
        q.push({x, y});
    }
}
 
void melt()
{
    int size = q.size();
    
    while(size--)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        map[x][y] = 2;
    }
}
 
int check()
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 1)
            {
                return 0;
            }
        }
    }
    
    return 1;
}
 
int main(void)
{
//    freopen("B2638_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
        }
    }
    
    // 치즈는 1, 바깥쪽은 2, 안쪽은 3~ 색칠 
    int level = 2;
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 0)
            {
                paint(i, j, level);
                level++;    
            }
        }
    }
    
    while(1)
    {    
        memset(visited, 0, sizeof(visited));
        
        time++;
        
        // 바깥쪽과 2면 이상 접촉하는 치즈, 큐에 삽입 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 1)
                {
                    init(i, j);            
                }
            }
        }
        
        melt();
        
        // 치즈가 녹아서 바깥쪽과 안쪽이 연결되었으면 다시 2로 색칠 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 2 && visited[i][j] == 0)
                {
                    paint(i, j, 2);
                }
            }
        }
        
        if(check() == 1)
        {
            cout << time;
            break;
        }
    }
    
    return 0;
}

#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
 
int map[110][110];
int visited[110][110];
int row, col;
int time;
 
queue<pair<int, int>> q;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < row && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void paint(int x, int y, int level)
{
    queue<pair<int, int>> c;
    c.push({x, y});
    visited[x][y] = 1;
    
    while(!c.empty())
    {
        int x = c.front().first;
        int y = c.front().second;
        c.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 1 && visited[xpos][ypos] == 0)
            {
                map[xpos][ypos] = level;
                c.push({xpos, ypos});
                visited[xpos][ypos] = 1;
            }
        }
    }
}
 
void init(int x, int y)
{
    int cnt = 0;
    
    for(int k = 0; k < 4; k++)
    {
        int xpos = x+dx[k];
        int ypos = y+dy[k];
        
        if(safe(xpos, ypos) == 1 && map[xpos][ypos] == 2)
        {
            cnt++;
        }
    }
    
    if(cnt >= 2)
    {
        q.push({x, y});
    }
}
 
void melt()
{
    int size = q.size();
    
    while(size--)
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        map[x][y] = 2;
    }
}
 
int check()
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 1)
            {
                return 0;
            }
        }
    }
    
    return 1;
}
 
int main(void)
{
//    freopen("B2638_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            cin >> map[i][j];
        }
    }
    
    // 치즈는 1, 바깥쪽은 2, 안쪽은 3~ 색칠 
    int level = 2;
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(map[i][j] == 0)
            {
                paint(i, j, level);
                level++;    
            }
        }
    }
    
    while(1)
    {    
        memset(visited, 0, sizeof(visited));
        
        time++;
        
        // 바깥쪽과 2면 이상 접촉하는 치즈, 큐에 삽입 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 1)
                {
                    init(i, j);            
                }
            }
        }
        
        melt();
        
        // 치즈가 녹아서 바깥쪽과 안쪽이 연결되었으면 다시 2로 색칠 
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(map[i][j] == 2 && visited[i][j] == 0)
                {
                    paint(i, j, 2);
                }
            }
        }
        
        if(check() == 1)
        {
            cout << time;
            break;
        }
    }
    
    return 0;
}