CS/Algorithm
[BOJ][C++] 14502 연구소
별토끼.
2019. 1. 12. 13:22
반응형
[BOJ][C++] 14502 연구소
문제
https://www.acmicpc.net/problem/14502
풀이
빈 칸마다 3개의 벽을 다 세워보고 바이러스를 퍼뜨려보는 식으로 문제를 풀었습니다.
브루트포스 방식으로 풀어서 시간 초과가 날 줄 알았는데 안나더라구요.
과거에 java로 풀어본 적이 있긴 한데 그 때는 참고를 해서 풀었다면 이번에는 제 힘으로 풀어서 더 뿌듯하고 좋았습니다.
코드
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int N, M;
int map[8][8];
int map_copy[8][8];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int max_value = 0;
void reset(int (*map1)[8], int (*map2)[8]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
map1[i][j] = map2[i][j];
}
}
}
void Virus() {
int virus_map[8][8];
reset(virus_map, map_copy);
queue<pair<int, int>> q;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (virus_map[i][j]==2) {
q.push(make_pair(i, j));
}
}
}
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
if (virus_map[nx][ny] == 0) {
virus_map[nx][ny] = 2;
q.push(make_pair(nx, ny));
}
}
}
int res = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (virus_map[i][j] == 0) {
res+=1;
}
}
}
max_value = max(max_value, res);
}
void Wall(int cnt) {
if (cnt == 3) {
Virus();
return;
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map_copy[i][j] == 0) {
map_copy[i][j] = 1;
Wall(cnt+1);
map_copy[i][j] = 0;
}
}
}
}
int main() {
scanf("%d %d", &N, &M);
for (int n = 0; n < N; n++) {
for (int m = 0; m < M; m++) {
scanf("%d", &map[n][m]);
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (map[i][j] == 0) {
reset(map_copy, map);
map_copy[i][j] = 1;
Wall(1);
map_copy[i][j] = 0;
}
}
}
printf("%d\n", max_value);
return 0;
}
반응형