문제접근![](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACH5BAEAAAAALAAAAAABAAEAAAICRAEAOw==)
놓쳤던 부분![](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACH5BAEAAAAALAAAAAABAAEAAAICRAEAOw==)
•
bfs함수에서 유효한 범위를 체크하는 부분 오류..
nx ≥ 0 ny ≥ 0
코드![](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACH5BAEAAAAALAAAAAABAAEAAAICRAEAOw==)
2028 KB
264 ms
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
int n, m;
int answer;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
std::vector<std::vector <int> > lab;
std::vector<std::vector <int> > copy_lab;
std::vector<std::vector <int> > virus_lab;
void input_setting()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
void input()
{
std::cin >> n >> m;
lab.resize(n, std::vector<int>(m));
copy_lab.resize(n, std::vector<int>(m));
virus_lab.resize(n, std::vector<int>(m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
std::cin >> lab[i][j];
}
void init_lab()
{
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
copy_lab[i][j] = lab[i][j];
}
void init_for_virus()
{
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
virus_lab[i][j] = copy_lab[i][j];
}
void bfs()
{
int count = 0;
std::queue<std::pair<int, int> > q;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (lab[i][j] == 2)
q.push({i, j});
while (!q.empty())
{
int x, y;
x = q.front().second;
y = q.front().first;
q.pop();
for (int i = 0; i < 4; i++)
{
int ny = y + dy[i];
int nx = x + dx[i];
if (ny >= 0 && nx >= 0 && ny < n && nx < m && virus_lab[ny][nx] == 0)
{
virus_lab[ny][nx] = 2;
q.push({ny, nx});
}
}
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (virus_lab[i][j] == 0)
++count;
answer = std::max(answer, count);
}
void dfs(int depth)
{
if (depth == 3)
{
init_for_virus();
bfs();
return ;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (copy_lab[i][j] == 0)
{
copy_lab[i][j] = 1;
dfs(depth + 1);
copy_lab[i][j] = 0;
}
}
void solution()
{
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
if (lab[i][j] == 0)
{
init_lab();
copy_lab[i][j] = 1;
dfs(1);
copy_lab[i][j] = 0;
}
}
}
void print()
{
std::cout << answer;
}
int main(void)
{
input_setting();
input();
solution();
print();
}
C++
복사