[BOJ] 14502 : 연구소
풀이
조합 BFS
삼성기출 변형문제
전형적인 삼성SW역량테스트 문제이다.
벽을 3개 세울수 있는 모든 경우 조합을 짠뒤, 가스가 이동할 수 있는 곳을 BFS로 탐색하면 된다.
그리고도 남은 0의 개수를 세서, 최대의 0이 남는 경우가 정답이다.
조합 짜는 부분을 첫번째는 매개변수 1개를 인덱스로 넘겨서 이렇게 짜고,(본문 코드)
int x = idx / m;
int y = idx % m;
if (arr[x][y] != 0) {
go(idx + 1, cnt);
}
else {
arr[x][y] = 1;
go(idx + 1, cnt + 1);
arr[x][y] = 0;
go(idx + 1, cnt);
}
두번째는 sx,sy를 넘겨가면서 2중반복문으로 이렇게 짰다.
시간은 동일하다.
for (int i = sx; i < n; i++) {
for (int j = sy; j < m; j++) {
if (arr[i][j] == 0) {
arr[i][j] = 1;
go(i, j, cnt + 1);
arr[i][j] = 0;
}
}
sy = 0;
}
코드
#include <iostream>
#include <queue>
#include <deque>
#include <vector>
#include <cstring>
using namespace std;
int n, m;
//0:빈칸 1:벽 2:바이러스
int arr[8][8];
int arr2[8][8];
int ans = 0;
const int dx[] = { -1,0,1,0 };
const int dy[] = { 0,1,0,-1 };
queue<pair<int, int>> virus;
void go(int idx, int cnt) {
if (cnt == 3) {
int sum = 0;
memcpy(arr2,arr,sizeof(arr));
queue<pair<int, int>> q = virus;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = x + dx[dir];
int ny = y + dy[dir];
if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
if (arr2[nx][ny] == 0) {
arr2[nx][ny] = 2;
q.push({ nx,ny });
}
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
//cout << arr2[i][j]<<' ';
if (arr2[i][j] == 0)
sum++;
}
//cout << '\n';
}
if (sum > ans)
ans = sum;
return;
}
if (idx >= n*m) {
return;
}
int x = idx / m;
int y = idx % m;
if (arr[x][y] != 0) {
go(idx + 1, cnt);
}
else {
arr[x][y] = 1;
go(idx + 1, cnt + 1);
arr[x][y] = 0;
go(idx + 1, cnt);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//벽을 3개 세울수 있을때 최대 안전영역 찾기
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> arr[i][j];
if (arr[i][j] == 2) {
virus.push({i,j});
}
}
}
go(0,0);
cout << ans;
return 0;
}
Written on April 12, 2019