백준 2636번 치즈 ( C++ )

문제

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

2636번: 치즈

해설

탐색 -> 1을 만날시 해당 값을 변경후 탐색을 멈추도록 구현

bfs / dfs 둘다 가능 => dfs선택 (bfs선택시 메모리 초과 조심)

코드

#include <bits/stdc++.h>
using namespace std;
 
int xx, yy, mp[104][104], visited[104][104], ret1, ret2;
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
queue<pair<int, int>> q;
 
int countSize()
{
  int countSize = 0;
  for (int i = 0; i < yy; i++)
  {
    for (int j = 0; j < xx; j++)
    {
      if (mp[i][j] == 1)
        countSize++;
    }
  }
  return countSize;
}
 
void dfs(int y, int x)
{
  visited[y][x] = 1;
  for (int i = 0; i < 4; i++)
  {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if (nx < 0 || ny < 0 || nx >= xx || ny >= yy || visited[ny][nx] == 1)
      continue;
    else if (mp[ny][nx] == 1)
    {
      mp[ny][nx] = 0;
      visited[ny][nx] = 1;
    }
    else if (mp[ny][nx] == 0)
      dfs(ny, nx);
  }
}
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
 
  cin >> yy >> xx;
  for (int i = 0; i < yy; i++)
  {
    for (int j = 0; j < xx; j++)
    {
      cin >> mp[i][j];
    }
  }
  while (true)
  {
    int cnt = countSize();
    if (cnt == 0)
    {
      break;
    }
    else
      ret2 = cnt;
    fill(&visited[0][0], &visited[0][0] + 104 * 104, 0);
    dfs(0, 0);
    ret1++;
  }
  cout << ret1 << "\n"
       << ret2;
}