[백준] 2636 치즈

#include "bits/stdc++.h"

using namespace std;

int sero, garo;

vector<vector<int>>cMap;
vector<pair<int, int>>edgePos;
vector < pair<int, int>> cPos;

int lastcheeseCount = 0;
int meltTimes = 0;

bool visited[100][100];

int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };

enum ETile
{
    Blank,
    Cheese,
    Edge,
    Out,
    Melt,
};

void SetOut(int y, int x)
{
    visited[y][x] = true;
    cMap[y][x] = ETile::Out;

    for (int a = 0;a < 4;a++)
    {
        int ny = y + dy[a];
        int nx = x + dx[a];

        if (ny < 0 || nx < 0 || ny >= sero || nx >= garo 
            ||  visited[ny][nx] 
            || cMap[ny][nx] == ETile::Cheese
            || cMap[ny][nx]== ETile::Edge)
        {
            continue;
        }

        SetOut(ny, nx);
    }
}

bool CanMelt(int y, int x)
{
   bool flag = false;

    for (int a = 0;a < 4;a++)
    {
        int ny = y + dy[a];
        int nx = x + dx[a];

        if (!(ny < 0 || nx < 0 || ny >= sero || nx >= garo))  
        {
            if (cMap[ny][nx] == ETile::Out 
                || cMap[ny][nx] == ETile::Edge)
                flag = true;
        }
    }
    
    return flag;
}

void Melting()
{
    int y = 0;
    int x = 0;

    for (auto line : cMap)
    {
        for (auto state : line)
        {
            if (state == ETile::Melt)
            {
                cMap[y][x] = ETile::Out;
            }

            x++;
        }

        x = 0;
        y += 1;
    }
}

void InitVisited()
{
    for (int a = 0;a < 100;a++)
    {
        for (int b = 0;b < 100;b++)
        {
            visited[a][b] = false;
        }
    }
}

void SetEdgePos()
{
    for (int a = 1;a < garo-2;a++)
    {
        edgePos.push_back(make_pair(1, a));
    
    }

    for (int a = 1;a < sero-2;a++)
    {
        edgePos.push_back(make_pair(a, 1));
      
    }

    for (int a = 0;a < garo-2;a++)
    {
        edgePos.push_back(make_pair(sero-2, garo-2-a));

    }

    for (int a = 0;a < sero-2;a++)
    {
        edgePos.push_back(make_pair(sero-2-a, garo-2));
        
    }
}

void SetEdge()
{
    for (int a = 0;a < garo;a++)
    {
        cMap[0][a] = ETile::Edge;   
    }

    for (int a = 0;a < sero;a++)
    {
      
        cMap[a][0] = ETile::Edge;
    }

    for (int a = 0;a < garo;a++)
    { 
        cMap[sero-1][garo-1-a] = ETile::Edge;
    }

    for (int a = 0;a < sero;a++)
    {
        cMap[sero-1-a][garo-1] = ETile::Edge;
    }
}

void PrintMap()
{
    cout<<endl;

    for (auto a : cMap)
    {
        for (auto b : a)
        {
            cout << b << " ";
        }
        cout << endl;
    }
}

void SetCheesePos()
{
    int y = 0;
    int x = 0;

    cPos.clear();

    for (auto line : cMap)
    {
        for (auto state :line )
        {
            if (state == ETile::Cheese)
            {
                cPos.push_back(make_pair(y, x));
            }

            x++;
        } 

        x = 0;
        y += 1;
    }
}

int GetCheeseCount()
{
    int cnt = 0;

    for (auto line : cMap)
    {
        for (auto state : line)
        {
            if (state == ETile::Cheese)
            {
                cnt++;
            }
        }
    }

    return cnt;
}

int main() {
    
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> sero >> garo;
    cin.ignore();


    for (int a = 0;a < sero;a++)
    {
        string input;
        vector<int> line;
        getline(cin, input);
        
        for (char ch : input)
        {
            if (ch != ' ')
            {
                line.push_back(ch - '0');
            }
        }
       
        cMap.push_back(line);
    }

    SetEdge();
    SetEdgePos();


    while (true)
    {
        InitVisited();
        SetCheesePos();

        int cheeseCount = GetCheeseCount();

        if (cheeseCount == 0)
        {
            break;
        }

        lastcheeseCount = cheeseCount;

        for (auto pos : edgePos)
        {
            if (cMap[pos.first][pos.second] != ETile::Cheese)
                SetOut(pos.first, pos.second);
        }

        //melt판별
        for (auto pos : cPos)
        {
            if (CanMelt(pos.first, pos.second))
            {
                cMap[pos.first][pos.second] = ETile::Melt;
            }
        }

        Melting();
        meltTimes++;
    }


    cout << meltTimes << endl <<lastcheeseCount ;
  
    

    return 0;
}

 

여러모로 고민을 많이 했던 문제였습니다.

 

로직은 다 제대로 짜두고 사소한 부분때문에 시간이 많이 빼았겼는데요

 

기억하고 넘어갈만한 포인트를 정리해보도록 하겠습니다.

 

우선 이 문제는 공백을 포함한 int값을 입력으로 주기 때문에 

 

getline을 이용해서 입력을 받고 후에 '0'을 빼줌으로 int값으로 바꾸는 과정을 거쳤습니다.

(ASCII코드상 문자 '1'에서 '0'을 빼면 정수가 나옵니다.)

   for (int a = 0;a < sero;a++)
   {
       string input;
       vector<int> line;
       getline(cin, input);
       
       for (char ch : input)
       {
           if (ch != ' ')
           {
               line.push_back(ch - '0');
           }
       }
      
       cMap.push_back(line);
   }

 

또한 문제에서 원하는 결과는 마지막으로 녹기 직전에 있던 치즈의 수와 녹을때 까지 걸린 시간입니다.

 

이부분을 코드로 옮기는 부분이 조금 미숙하여서 lastcheeseCount와 meltimes를 초기화 하는 순서에 혼선이 있었습니다.

 

아래처럼 짜야만 lastcheeseCount에는 이전의 치즈의 수가 저장되고 녹인 횟수도 명확하게 추적이 됩니다.

 

  while (true)
  {
      InitVisited();
      SetCheesePos();

      int cheeseCount = GetCheeseCount();

      if (cheeseCount == 0)
      {
          break;
      }

      lastcheeseCount = cheeseCount;

      for (auto pos : edgePos)
      {
          if (cMap[pos.first][pos.second] != ETile::Cheese)
              SetOut(pos.first, pos.second);
      }

      //melt판별
      for (auto pos : cPos)
      {
          if (CanMelt(pos.first, pos.second))
          {
              cMap[pos.first][pos.second] = ETile::Melt;
          }
      }

      Melting();
      meltTimes++;
  }

 

또한 고민이 많았던 부분은 어떠한 방식으로 테두리의 치즈를 파악할것인가 였습니다.

 

저의 최종적인 결론은 상하좌우를 검사해서 Out이라면 테두리라고 판단하였습니다.

 

Out은 각 모서리에서 치즈가 없는 부분을 dfs로 찾았습니다.