인프런 커뮤니티 질문&답변
작성한 질문수
2-P 왜 예제에서 0이 나올까요..?
작성
·
103
0
코드가 아래와 같은데 뭐가 잘못된 걸까요..?ㅜ
#include <iostream>
#include <string>
#include <vector>
#include <queue>
int calcArea(const std::vector<std::vector<int>> &map)
{
int result = 0;
for(int i = 0; i < map.size(); ++i)
{
for (int j = 0; j < map[i].size(); ++j)
{
if (map[i][j] == 0) result += 1;
}
}
return result;
}
void bfs(std::vector<std::vector<int>> &map, std::vector<std::vector<bool>> &visited, const int yy, const int xx)
{
std::queue<std::pair<int, int>> que;
visited[yy][xx] = true;
que.push({yy, xx});
int y, x;
int moveX[4] = {0, 0, -1, 1};
int moveY[4] = {1, -1, 0, 0};
while(!que.empty())
{
y = que.front().first;
x = que.front().second;
que.pop();
for(int i = 0; i < 4; ++i)
{
int newX = x + moveX[i];
int newY = y + moveY[i];
if (newX >= 0 && newX < map[0].size() && newY >= 0 && newY < map.size() && !visited[newY][newX] && map[newY][newX] != 1)
{
que.push({newY, newX});
visited[newY][newX] = true;
map[newY][newX] = 2;
}
}
}
}
int solve(std::vector<std::vector<int>> map, const std::vector<std::pair<int, int>>& virusList)
{
std::vector<std::vector<bool>> visited(map.size());
std::vector<bool> temp(map[0].size());
temp.assign(temp.size(), false);
visited.assign(visited.size(), temp);
for(int i = 0; i < virusList.size(); ++i)
{
bfs(map, visited, virusList[i].first, virusList[i].second);
}
return calcArea(map);
}
int solution(std::vector<std::vector<int>> map, const std::vector<std::pair<int, int>>& wallList, const std::vector<std::pair<int, int>>& virusList)
{
int result = 0;
for(int i = 0; i < wallList.size(); ++i)
{
for (int j = 0; j < i; ++j)
{
for (int k = 0; k < j; ++k)
{
map[wallList[i].first][wallList[i].second] = 1;
map[wallList[j].first][wallList[j].second] = 1;
map[wallList[k].first][wallList[k].second] = 1;
result = std::max(result, solve(map, virusList));
map[wallList[i].first][wallList[i].second] = 0;
map[wallList[j].first][wallList[j].second] = 0;
map[wallList[k].first][wallList[k].second] = 0;
}
}
}
return result;
}
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int N, M;
std::cin >> N >> M;
std::string str;
std::vector<std::vector<int>> map;
int temp;
std::vector<std::pair<int, int>> wallList, virusList;
for (int i = 0; i < N; ++i)
{
std::vector<int> tempVec;
for(int j = 0; j < M; ++j)
{
std::cin >> temp;
if (temp == 1) wallList.push_back({i, j});
else if (temp == 2) virusList.push_back({i, j});
tempVec.push_back(temp);
}
map.push_back(tempVec);
}
int result = 0;
result = solution(map, wallList, virusList);
std::cout << result << std::endl;
return 0;
}
답변 3
1
초기화부분, 기존에 벽을 기반으로 하는게 아니라 -> 벽이 없는 곳에 있는 지역에 벽을 세움.
이 로직 등을 다듬어 봤습니다. 참고부탁드립니다.
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
int calcArea(const std::vector<std::vector<int>>& map)
{
int result = 0;
for (int i = 0; i < map.size(); ++i)
{
for (int j = 0; j < map[i].size(); ++j)
{
if (map[i][j] == 0)
result += 1;
}
}
return result;
}
void bfs(std::vector<std::vector<int>>& map, std::vector<std::vector<bool>>& visited, const int yy, const int xx)
{
std::queue<std::pair<int, int>> que;
visited[yy][xx] = true;
que.push({yy, xx});
int y, x;
int moveX[4] = {0, 0, -1, 1};
int moveY[4] = {1, -1, 0, 0};
while (!que.empty())
{
y = que.front().first;
x = que.front().second;
que.pop();
for (int i = 0; i < 4; ++i)
{
int newX = x + moveX[i];
int newY = y + moveY[i];
if (newX >= 0 && newX < map[0].size() && newY >= 0 && newY < map.size() && !visited[newY][newX] && map[newY][newX] != 1)
{
que.push({newY, newX});
visited[newY][newX] = true;
map[newY][newX] = 2;
}
}
}
}
int solve(std::vector<std::vector<int>> map, const std::vector<std::pair<int, int>>& virusList)
{
std::vector<std::vector<bool>> visited(map.size(), std::vector<bool>(map[0].size(), false));
for (int i = 0; i < virusList.size(); ++i)
{
bfs(map, visited, virusList[i].first, virusList[i].second);
}
return calcArea(map);
}
int solution(std::vector<std::vector<int>> map, const std::vector<std::pair<int, int>>& emptySpaces, const std::vector<std::pair<int, int>>& virusList)
{
int result = 0;
for (int i = 0; i < emptySpaces.size(); ++i)
{
for (int j = i + 1; j < emptySpaces.size(); ++j)
{
for (int k = j + 1; k < emptySpaces.size(); ++k)
{
map[emptySpaces[i].first][emptySpaces[i].second] = 1;
map[emptySpaces[j].first][emptySpaces[j].second] = 1;
map[emptySpaces[k].first][emptySpaces[k].second] = 1;
result = std::max(result, solve(map, virusList));
map[emptySpaces[i].first][emptySpaces[i].second] = 0;
map[emptySpaces[j].first][emptySpaces[j].second] = 0;
map[emptySpaces[k].first][emptySpaces[k].second] = 0;
}
}
}
return result;
}
int main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
int N, M;
std::cin >> N >> M;
std::vector<std::vector<int>> map(N, std::vector<int>(M));
std::vector<std::pair<int, int>> emptySpaces, virusList;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < M; ++j)
{
std::cin >> map[i][j];
if (map[i][j] == 0)
emptySpaces.push_back({i, j});
else if (map[i][j] == 2)
virusList.push_back({i, j});
}
}
int result = solution(map, emptySpaces, virusList);
std::cout << result << std::endl;
return 0;
}
0
0
안녕하세요 hello님 ㅎㅎ
이렇게 질문주시면 제가 디버깅하기가 너무 힘듭니다. (들여쓰기가 안되어있어욤 ㅠ)
0주차 - 질문하는 방법 참고해서 질문 부탁드립니다.
감사합니다.
