[백준] 14502번 연구소 C++ 코드

코드

#include <bits/stdc++.h>
using namespace std;
int n,m,res,cnt;
int graph[14][14];
int visited[14][14]; // 매번 업데이트 시켜줘야함
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
vector<pair<int, int>> wall;
vector<pair<int, int>> virus;

void dfs(int x, int y) {
  visited[x][y] = 1;
  for(int i = 0; i < 4; i++) {
    int nx = x + dx[i];
    int ny = y + dy[i];
    if(nx >= n || ny >= m || nx < 0 || ny < 0) continue;
    if (graph[nx][ny] != 1 && !visited[nx][ny]) dfs(nx,ny);
  }
}

int solve() {
  int temp = 0;
  for(int i = 0; i < virus.size(); i++) {
    dfs(virus[i].first, virus[i].second);
  }
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      if((visited[i][j] == 0)&&graph[i][j]==0) temp++;
    }
  }
  memset(visited,0,sizeof(visited));
  return temp;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> m;
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      cin >> graph[i][j];
      if (graph[i][j] == 2) virus.push_back({i,j});
      if (graph[i][j] == 0) wall.push_back({i,j});
    }
  }
  for(int i = 0; i < wall.size(); i++) {
    for(int j = i+1; j < wall.size(); j++) {
      for(int k = j + 1; k < wall.size(); k++) {
        graph[wall[i].first][wall[i].second] = 1;
        graph[wall[j].first][wall[j].second] = 1;
        graph[wall[k].first][wall[k].second] = 1;
        cnt = solve();
        res = max(cnt,res);
        graph[wall[i].first][wall[i].second] = 0;
        graph[wall[j].first][wall[j].second] = 0;
        graph[wall[k].first][wall[k].second] = 0;
      }
    }
  }
  cout << res << '\n';
  return 0;
}

해줘야 할 일이 조금 더 많아진 dfs문제. 벽 3개를 어떻게 세울지 구상하면 쉽게 해결할 수 있다. 벡터를 이용해 빈 공간을 저장해두고 3개를 뽑는 것에 벽을 느꼈다. 그래도 접근 방식을 이해했으니 큰 수확을 얻은 듯하다.