[BOJ] 14502번 : 연구소

1. problem : 

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

 

2. solution 1 :

#include <bits/stdc++.h>
using namespace std;
#define X first 
#define Y second 
int n, m; 
int board[10][10];  //400byte 원본
int board2[10][10]; // 400byte 사본 -> 자유롭게 수정가능
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
vector<pair<int, int>> viruse;
vector<int> wall;
int ans;

void bfs() {
	queue<pair<int, int>> Q;
	for (auto v : viruse) {
		Q.push({ v.X,v.Y });
	}
	while (!Q.empty()) {
		auto cur = Q.front(); Q.pop(); 
		for (int dir = 0; dir < 4; dir++) {
			int nx = cur.X + dx[dir]; 
			int ny = cur.Y + dy[dir]; 
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; 
			if ( board2[nx][ny] == 2 || board2[nx][ny] == 1) continue; 
			board2[nx][ny] = 2; 
			Q.push({ nx,ny });
		}
	}
}
void safe_zone_cnt() {
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (board2[i][j] == 0)  cnt++;
		}
	}
	ans = max(ans, cnt);
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> board[i][j];
			if (board[i][j] == 2) viruse.push_back({ i,j });
			board2[i][j] = board[i][j];
		}
	}
	wall.resize(n * m);  // 벽 벡터 크기 조정
	fill(wall.begin() + n * m - 3, wall.begin() + n*m, 1);
	do {
		bool isdup = false;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) board2[i][j] = board[i][j];
		}
		vector<pair<int, int>> wall_xy;
		for (int i = 0; i < n*m; i++) {
			if (wall[i] == 1) {
				int x = i / m; 
				int y = i % m;
				if (board2[x][y] != 0) {
					isdup = true; 
					break;
				}
				wall_xy.push_back({ x,y });
			}
		}
		if (!isdup) {
			for (auto s : wall_xy) {
				board2[s.X][s.Y] = 1;
			}
			// bfs 실행 
			bfs();
			safe_zone_cnt();
		}
	} while (next_permutation(wall.begin(), wall.end()));

	cout << ans;

}

 

3. solution 2 : 

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : jihwan0123
// http://boj.kr/b4a6eb773dd245e88475502d0b25d168
#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int board[8][8];
int n, m, ans;
int free_cells = 0;
queue<pair<int, int>> virus;  // 바이러스
vector<pair<int, int>> frees; // 빈칸
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

// 바이러스가 전파된 칸의 수를 반환
int bfs() {
  queue<pair<int, int>> q;
  bool vis[8][8] = {};
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(board[i][j] == 2) q.push({i, j});
    }
  }
  int ret = 0;
  while (!q.empty()) {
    pair<int, int> cur = q.front();
    q.pop();
    ret++;
    for (int i = 0; i < 4; i++) {
      int nx = cur.X + dx[i];
      int ny = cur.Y + dy[i];
      if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
      if (board[nx][ny] != 0 || vis[nx][ny]) continue;
      vis[nx][ny] = 1;
      q.push({nx, ny});      
    }
  }
  return ret;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> board[i][j];
      if (board[i][j] == 0) {     // 빈 칸 개수와 좌표 저장
        free_cells++;
        frees.push_back({i, j});
      } else if (board[i][j] == 2) // 바이러스 좌표 저장
        virus.push({i, j});
    }
  }
  for(int i = 0; i < frees.size(); i++){
    board[frees[i].X][frees[i].Y] = 1;
    for(int j = i + 1; j < frees.size(); j++){
      board[frees[j].X][frees[j].Y] = 1;
      for(int k = j + 1; k < frees.size(); k++){
        board[frees[k].X][frees[k].Y] = 1;
        // 바이러스 퍼진 개수 체크
        int tmp = bfs();
        // 안전영역 = 빈칸 - 바이러스 퍼진 칸, 3을 빼는 이유는 벽을 3개 세웠으므로.
        ans = max(free_cells - 3 - tmp + (int)virus.size(), ans);
        board[frees[k].X][frees[k].Y] = 0;
      }
      board[frees[j].X][frees[j].Y] = 0;
    }
    board[frees[i].X][frees[i].Y] = 0;
  }  
  cout << ans;
}
/*
3중 for문을 이용해 빈칸 중에서 3개씩 벽으로 바꿔보면서 최대 크기 계산
*/

source code 출처 : https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0D/solutions/14502.cpp

basic-algo-lecture/0x0D/solutions/14502.cpp at master · encrypted-def/basic-algo-lecture

 

 

4. solution 3 :

// Authored by : jihwan0123
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/c7974a009076431aaebdf25b5792144f
#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int board[8][8];
int n, m, ans;
int free_cells = 0;
queue<pair<int, int>> virus;  // 바이러스
vector<pair<int, int>> frees; // 빈칸
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

// 바이러스가 전파된 칸의 수를 반환
int bfs() {
  queue<pair<int, int>> q;
  bool vis[8][8] = {};
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(board[i][j] == 2) q.push({i, j});
    }
  }
  int ret = 0;
  while (!q.empty()) {
    pair<int, int> cur = q.front();
    q.pop();
    ret++;
    for (int i = 0; i < 4; i++) {
      int nx = cur.X + dx[i];
      int ny = cur.Y + dy[i];
      if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
      if (board[nx][ny] != 0 || vis[nx][ny]) continue;
      vis[nx][ny] = 1;
      q.push({nx, ny});      
    }
  }
  return ret;
}

// k번째 벽의 위치를 선택, idx번째 빈 칸부터 고려
void dfs(int k, int idx) {
  // 벽 3개 세웠으면 bfs로 확인
  if (k == 3) {
    // 바이러스 퍼진 개수 체크
    int tmp = bfs();
    // 안전영역 = 빈칸 - 바이러스 퍼진 칸, 3을 빼는 이유는 벽을 3개 세웠으므로.
    ans = max(free_cells - 3 - tmp + (int)virus.size(), ans);
    return;
  }
  // 각 빈 칸을 벽으로 변경해서 백트래킹 진행
  for (int i = idx; i < frees.size(); i++) {
    board[frees[i].X][frees[i].Y] = 1;
    dfs(k + 1, i + 1);
    board[frees[i].X][frees[i].Y] = 0;
  }
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> board[i][j];
      if (board[i][j] == 0) {     // 빈 칸 개수와 좌표 저장
        free_cells++;
        frees.push_back({i, j});
      } else if (board[i][j] == 2) // 바이러스 좌표 저장
        virus.push({i, j});
    }
  }
  dfs(0, 0);
  cout << ans;
}
/*
백트래킹을 이용해 빈칸 중에서 3개씩 벽으로 바꿔보면서 최대 크기 계산
*/

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x0D/solutions/14502_1.cpp

basic-algo-lecture/0x0D/solutions/14502_1.cpp at master · encrypted-def/basic-algo-lecture

매력적인 풀이