백준 14502번 연구소 ( C++ )

문제

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

14502번: 연구소

 

해설

bfs / dfs 둘다 가능

모든 경우의 수를 구해야하는 문제....(n,m크기 && 시간초 보고 빠르게 판단해야함)

무식하게 접근하는게 답이였다. => 그 과정에서 여러 변수들을 잘 통제해야함

 

코드

#include <bits/stdc++.h>
using namespace std;
 
int n, m, mp[8][8], num, visited[8][8];
int ret = 0;
int cnt = 0;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
vector<pair<int, int>> zero, two;
 
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 >= m || ny >= n || mp[ny][nx] == 1 || visited[ny][nx] == 1)
      continue;
    dfs(ny, nx);
  }
  return;
}
 
int main()
{
  cin >> n >> m;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      cin >> num;
      mp[i][j] = num;
      if (num == 2)
        two.push_back({i, j});
      else if (num == 0)
        zero.push_back({i, j});
    }
  }
 
  int s = zero.size();
  for (int i = 0; i < s; i++)
  {
    for (int j = i + 1; j < s; j++)
    {
      for (int k = j + 1; k < s; k++)
      {
        mp[zero[i].first][zero[i].second] = 1;
        mp[zero[j].first][zero[j].second] = 1;
        mp[zero[k].first][zero[k].second] = 1;
        fill(&visited[0][0], &visited[0][0] + 8 * 8, 0);
        cnt = 0;
        for (pair<int, int> p : two)
        {
          if (visited[p.first][p.second] == 0)
            dfs(p.first, p.second);
        }
        for (int i = 0; i < n; i++)
        {
          for (int j = 0; j < m; j++)
          {
            if (visited[i][j] == 0 && mp[i][j] == 0)
              cnt++;
          }
        }
        ret = max(ret, cnt);
        mp[zero[i].first][zero[i].second] = 0;
        mp[zero[j].first][zero[j].second] = 0;
        mp[zero[k].first][zero[k].second] = 0;
      }
    }
  }
  cout << ret;
}