2-P 왜 예제에서 0이 나올까요..?
210
작성한 질문수 13
코드가 아래와 같은데 뭐가 잘못된 걸까요..?ㅜ
#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
안녕하세요 hello님 ㅎㅎ
이렇게 질문주시면 제가 디버깅하기가 너무 힘듭니다. (들여쓰기가 안되어있어욤 ㅠ)
0주차 - 질문하는 방법 참고해서 질문 부탁드립니다.
감사합니다.
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;
}2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
7
2
2주차 개념#12 트리 순회
0
19
2
백준사이트가 종료된다고 합니다.
0
225
2
백준 서비스 종료
9
719
1
sk 하이닉스 코테 대비
0
352
2
3-G 최댓값 질문
0
50
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
82
2
3-I 코드 질문드립니다.
0
61
2
3-N 질문 있습니다.
0
66
2
학습방법
0
100
2
4-H 질문 있습니다 (코드 리뷰)
0
66
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
164
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
69
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
63
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
49
2
조합 재귀 풀이 확인 해주시면 감사하겠습니다.
0
67
2
함수별 시간복잡도
0
72
2
3-h 질문입니다.
0
49
1
안녕하세요 선생님. 시간 복잡도 4번 질문있습니다.
0
52
2
1-I 문제 질문 드립니다.
0
76
2
2-P 질문입니다.
0
56
1
mac에서 시작하기 관련
0
88
2
5-Q 질문
0
63
2
풀이 코드 질문
0
63
2