[백준] 14502번 연구소

14502번 연구소

---

1. 이해하기

• 연구소에 바이러스가 퍼지지 않도록 벽을 세워야 한다. 벽은 꼭 3개를 세워야 한다.
• 바이러스는 상하좌우로 인접한 빈 칸으로 퍼져나간다.
• 바이러스가 벽으로 인해서 퍼져나갈 수 없는 영역을 안전영역이라 한다. 안전 영역 크기의 최댓값을 구해야 한다.

---

2. 구현하기

• 바이러스는 상하좌우로 인접한 빈 칸으로 퍼져나간다.

  • BFS를 이용하여 바이러스의 이동을 구현한다.

    void bfs(int r, int c) {
        queue<Point> q;
        q.push({r,c});
        visited[r][c] = true;
    
        while(!q.empty()) {
            int x = q.front().x,y = q.front().y; q.pop();
            for(int i = 0; i < 4; i++) {
                int nx = x+dx[i], ny = y+dy[i];
                if(is_out_bound(nx,ny) or visited[nx][ny] or map[nx][ny] == 1) continue;
                visited[nx][ny] = true;
                q.push({nx,ny});
            }
        }
    }

• 바이러스가 퍼지지 않도록 3개의 벽을 세우고 그때 안전한 지역이 몇개인지 센다.

  int count_safe_area() {
      int ret = 0;
      for(int i = 0; i < N; i++) {
          for(int j = 0; j < M; j++) {
              if(!visited[i][j] and map[i][j] == 0) ret++;
          }
      }
      return ret;
  }
  
  int solve(int cnt, int index) {
      if(cnt == 3) {
          memset(visited,false,sizeof(visited));
          for(int i = 0; i < N; i++) {
              for(int j = 0; j < M; j++) {
                  if(visited[i][j]) continue;
                  if(map[i][j] == 2) {
                      bfs(i,j);
                  }
              }
          }
          return count_safe_area();
      }
  
      int ret = 0;
      for(int i = index; i < N*M; i++) {
          int x = i/M, y = i%M;
          if(map[x][y] != 0) continue;
          map[x][y] = 1;
          ret = max(ret,solve(cnt+1,i+1));
          map[x][y] = 0;
      }
      return ret;
  }

---

3. 전체 코드

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
struct Point{
    int x,y;
};
int map[8][8];
bool visited[8][8];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int N,M;

bool is_out_bound(int x, int y) {
    return x < 0 or x >= N or y < 0 or y >= M;
}

void bfs(int r, int c) {
    queue<Point> q;
    q.push({r,c});
    visited[r][c] = true;

    while(!q.empty()) {
        int x = q.front().x,y = q.front().y; q.pop();
        for(int i = 0; i < 4; i++) {
            int nx = x+dx[i], ny = y+dy[i];
            if(is_out_bound(nx,ny) or visited[nx][ny] or map[nx][ny] == 1) continue;
            visited[nx][ny] = true;
            q.push({nx,ny});
        }
    }
}

int count_safe_area() {
    int ret = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(!visited[i][j] and map[i][j] == 0) ret++;
        }
    }
    return ret;
}

int solve(int cnt, int index) {
    if(cnt == 3) {
        memset(visited,false,sizeof(visited));
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(visited[i][j]) continue;
                if(map[i][j] == 2) {
                    bfs(i,j);
                }
            }
        }
        return count_safe_area();
    }

    int ret = 0;
    for(int i = index; i < N*M; i++) {
        int x = i/M, y = i%M;
        if(map[x][y] != 0) continue;
        map[x][y] = 1;
        ret = max(ret,solve(cnt+1,i+1));
        map[x][y] = 0;
    }
    return ret;
}

int main() {
    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }

    cout << solve(0,0) << '\n';
    return 0;
}