[Algorithm] Baekjoon 2638번 : 치즈

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

2638번: 치즈

struct Node
{
    int y;
    int x;
};
 
int row, col;
int arr[101][101] = { 0 };
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
bool visited[101][101] = { false };
int curMeltedCheese = 0;
 
vector<Node> cheese;
 
void init()
{
    for (int i = 0; i < cheese.size(); ++i)
    {
        if (arr[cheese[i].y][cheese[i].x] == 2)
        {
            arr[cheese[i].y][cheese[i].x] = 1;
        }
    }
}
 
void BFS() 
{
    memset(visited, false, sizeof(visited));
    queue<Node> q;
    q.push({ 0,0 });
    visited[0][0] = true;
    int cheeseCount = 0;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x; 
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= row) continue;
            if (nextX < 0 || nextX >= col) continue;
            if (visited[nextY][nextX] == true) continue;
 
            if (arr[nextY][nextX] == 1) // 치즈칸에 첫번째 방문이면
            {
                arr[nextY][nextX] = 2; // 한번 방문했다고 표시
            }
            else if (arr[nextY][nextX] == 2) // 치즈칸에 두번째 방문이면
            {
                ++cheeseCount;
                visited[nextY][nextX] = true;
                arr[nextY][nextX] = 0;
            }
            else // 빈공간이면
            {
                q.push({ nextY,nextX });
                visited[nextY][nextX] = true;
            }
        }
    }
    
    curMeltedCheese = cheeseCount;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> row >> col;
 
    for (int i = 0; i < row; ++i)
    {
        for (int j = 0; j < col; ++j)
        {
            cin >> arr[i][j];
            
            if (arr[i][j] == 1)
            {
                cheese.push_back({ i,j });
            }
        }
    }
 
    int hour = 0;
 
    while (1)
    {
       BFS(); 
        init();
        if (curMeltedCheese == 0) break;
        ++hour;
    }
 
    cout << hour;
}

바로 이전에 풀었던 치즈문제에서 좀 더 발전된 문제다.

 

이전의 문제는 한변만 닿아도 바로 녹이는 문제였다면, 이번문제는 두 변이상이 닿아야 녹는 문제이다.

 

그래서 처음 치즈에 방문했을 때 1이였던 값을 2로 표시해놓고, 다시 해당 치즈에 방문했을 때 값이 2이면 녹이는 식으로 구현했다. 대신 단순히 이렇게 하면 한번 BFS 돌릴때마다 2인 치즈위치의 값을 1로 바꿔놔야 한다.

 

0,0부터 끝까지 순회하는건 시간낭비같아서 처음에 맵을 입력받을 때 치즈위치를 따로 저장해놨기 떄문에 해당 벡터만 순회하면서 2인걸 1로 바꿔주면 된다.

 

이렇게 해도 8ms라는 나쁘지않은 결과로 통과하기는 한다.

다만, 한번의 BFS마다 2인걸 1로 초기화시키는게 굳이 필요한가 싶어서 좀 더 생각을 한다음 코드를 작성해보았다.

struct Node
{
    int y;
    int x;
};
 
int row, col;
int arr[101][101] = { 0 };
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
bool visited[101][101] = { false };
int countCheck[101][101] = { 0 };
int curMeltedCheese = 0;
 
void BFS() 
{
    memset(visited, false, sizeof(visited));
    memset(countCheck, 0, sizeof(countCheck));
 
    queue<Node> q;
    q.push({ 0,0 });
    visited[0][0] = true;
    int cheeseCount = 0;
 
    while (!q.empty())
    {
        int curY = q.front().y;
        int curX = q.front().x; 
        q.pop();
 
        for (int i = 0; i < 4; ++i)
        {
            int nextY = curY + dir[i][0];
            int nextX = curX + dir[i][1];
 
            if (nextY < 0 || nextY >= row) continue;
            if (nextX < 0 || nextX >= col) continue;
            if (visited[nextY][nextX]) continue;
 
            if (arr[nextY][nextX] >= 1) // 치즈가 있는공간이면
            {
                if (countCheck[nextY][nextX] == 0) // 한번도 방문한 적 없으면
                {
                    countCheck[nextY][nextX] = 1; // 한번 방문했다고 표시.
                }
                else // 한번 방문한적이 있다면
                {
                    countCheck[nextY][nextX] = 2;
                    arr[nextY][nextX] = 0;
                    ++cheeseCount;
                    visited[nextY][nextX] = true;
                }
            }
            else // 빈공간이면
            {
                visited[nextY][nextX] = true;
                q.push({ nextY,nextX });
            }
        }
    }
    
    curMeltedCheese = cheeseCount;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> row >> col;
 
    for (int i = 0; i < row; ++i)
    {
        for (int j = 0; j < col; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    int hour = 0;
 
    while (1)
    {
        BFS(); // 일단 돌려서 녹은 치즈개수 체크.
        if (curMeltedCheese == 0) break;
        ++hour;
    }
 
    cout << hour;
}

 

 

맨 처음 코드와 달리 초기화하는 부분이 없고, 대신 체크를 하는 배열을 하나 더 추가했다.

통과는 하는데, 처음 코드와 수행속도는 동일하게 나오긴 했다;;

이것도 N,M값이 최대 100정도밖에 안되서 차이없다고 나오는거 같긴 하는데 값이 엄청 크면 그래도 차이가 있을 것이다.