BOJ 2638 - 치즈

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

재밌는 문제였다.

처음에는 외부공기와 접촉한 부분만 녹는다는 조건을 제대로 안보고, 그냥 두면이상이 공기와 접촉하면 녹이는 식으로 해서 틀렸다.

그리고나서 문제를 제대로 읽고, 외부공기와 접촉한 부분이 두면이상일 때 녹게하기 위해 어떻게 해야할지 고민을 좀 했다. 

이중반복문 완전탐색으로 가다가 치즈나오는 부분이 생기면 그때부터 bfs나 dfs로 치즈인 부분들만 탐색하게 할까, 어떻게해야할까 등등...

그러다가 외부공기만 먼저 오염(?)시키고 난 후에, (0,0 부터 시작해 dfs로 0인부분들만 찾아서 오염시킨다.) 외부와 접촉하는 부분이 두개이상인 부분을 큐에넣고 저장한다음, 큐안의 내용물들을 모두 녹이는 방법을 떠올려서 이렇게 풀었다! (큐에 넣는 이유는 두면이 접촉한다고 바로 녹여버려도... 이 문제에서 내가 푼 방법으로 하면 상관은 없을 것 같지만... 다른 문제들에서 여기서 바로 녹여버리면 1초후가 아니라 (시간상)지금 다른 치즈들에도 영향을 주기 때문에)

 

재밌었다.

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[104][104];
int cheeseCnt;
int dirY[4] = {1, -1, 0, 0};
int dirX[4] = {0, 0, 1, -1};
queue<pair<int, int>> q;
int visited[104][104];

void print()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cout << a[i][j] << " ";
        }
        cout << "\n";
    }
}

void dfs(int y, int x)
{
    // 외부공기표시
    visited[y][x] = 1;

    for (int i = 0; i < 4; i++)
    {
        int nextY = y + dirY[i];
        int nextX = x + dirX[i];
        if (nextY >= 0 && nextY < n && nextX >= 0 && nextX < m && !visited[nextY][nextX] && a[nextY][nextX] == 0)
        {
            dfs(nextY, nextX);
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> a[i][j];
            if (a[i][j] == 1)
            {
                cheeseCnt++;
            }
        }
    }

    int t = 0;
    // cout << "------\n";

    while (cheeseCnt)
    {
        memset(visited, 0, sizeof(visited));
        // print();
        // cout << "------\n";
        dfs(0, 0);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                int tmpCnt = 0;
                int y = i;
                int x = j;
                for (int k = 0; k < 4; k++)
                {
                    int nextY = y + dirY[k];
                    int nextX = x + dirX[k];
                    if (nextY < 0 || nextY >= n || nextX < 0 || nextX >= m || a[y][x] != 1)
                    {
                        break;
                    }
                    if (visited[nextY][nextX] == 1)
                    {
                        tmpCnt++;
                    }
                    if (tmpCnt >= 2)
                    {
                        q.push({y, x});
                        break;
                    }
                }
            }
        }

        while (q.size())
        {
            int y = q.front().first;
            int x = q.front().second;
            q.pop();
            a[y][x] = 0;
            cheeseCnt--;
        }
        t++;
    }
    cout << t << "\n";
    return 0;
}

/*
8 9
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 1 1 0
0 1 0 1 1 1 0 1 0
0 1 0 0 1 0 0 1 0
0 1 0 1 1 1 0 1 0
0 1 1 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0
*/

 

요즘 쉬운문제들을 좀 많이 풀었는데, 난이도 있는 문제들도 많이 풀도록 해야겠다.