문제링크 : https://www.codetree.ai/training-field/frequent-problems/problems/vaccine-for-virus/submissions?page=2&pageSize=20
💻 문제 풀이 : C++
#### 📌 정답풀이#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
struct Coord
{
int row, col;
};
int N, M;
// 원본
int MAP[55][55];
// 다음 시간 바이러스맵
int NEXT[55][55];
// 방문 표시
int visited[55][55];
// 바이러스 개수
int cnt;
int used[15];
int answer;
// 병원
vector<Coord> h;
// 바이러스
vector<Coord> v;
// M개 조합 병원
vector<Coord> s;
int dr[] = { 0, 0, -1, 1 };
int dc[] = { -1, 1, 0, 0 };
// 바이러스가 없는지 확인
int isClear(int MAP[55][55])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (MAP[i][j] == 0) return 0;
}
}
return 1;
}
void MapCopy(int A[55][55], int B[55][55])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
A[i][j] = B[i][j];
}
}
}
// 병원부터 출발해서 바이러스 제거하기
int ClearVirus()
{
// 지금 제거한 바이러스
int nowCnt = 0;
memset(visited, 0, sizeof(visited));
queue<Coord> nowQ;
for (int i = 0; i < s.size(); i++)
nowQ.push(s[i]);
while (!nowQ.empty())
{
Coord now = nowQ.front();
nowQ.pop();
for (int i = 0; i < 4; i++)
{
Coord n = { now.row + dr[i], now.col + dc[i] };
if (n.row < 0 || n.col < 0 || n.row >= N || n.col >= N) continue;
if (NEXT[n.row][n.col] == 1) continue;
if (visited[n.row][n.col] != 0) continue;
visited[n.row][n.col] = visited[now.row][now.col] + 1;
if (visited[n.row][n.col] >= answer) return answer;
// 3은 청소한 바이러스 표시
if (NEXT[n.row][n.col] == 0)
{
NEXT[n.row][n.col] = 3;
nowCnt++;
}
// 바이러스를 모두 제거
if (nowCnt == cnt)
{
return visited[n.row][n.col];
}
nowQ.push({ n.row, n.col });
}
}
// 모두 제거하지 못했으면
return 2134567890;
}
// M개의 병원 고르기
void dfs(int depth, int start)
{
if (depth == M)
{
MapCopy(NEXT, MAP);
answer = min(answer, ClearVirus());
return;
}
for (int i = start; i < h.size(); i++)
{
if (used[i] == 1) continue;
used[i] = 1;
s.push_back(h[i]);
dfs(depth + 1, start + 1);
s.pop_back();
used[i] = 0;
}
}
void CLEAR()
{
cnt = 0;
answer = 2134567890;
memset(MAP, 0, sizeof(MAP));
memset(NEXT, 0, sizeof(NEXT));
}
void INPUT()
{
cin >> N >> M;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> MAP[i][j];
if (MAP[i][j] == 0)
cnt++;
if (MAP[i][j] == 2)
{
h.push_back({ i, j });
}
}
}
}
void SOLVE()
{
// 바이러스가 없으면 0을 출력하고 종료
if (isClear(MAP))
{
cout << 0 << endl;
return;
}
// M개 병원 고르기
dfs(0, 0);
if (answer == 2134567890) cout << -1 << endl;
else cout << answer << endl;
}
int main()
{
CLEAR();
INPUT();
SOLVE();
return 0;
}😂 시간초과 코드
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
struct Coord
{
int row, col;
};
int N, M;
// 원본
int MAP[55][55];
// bfs를 위한 원본
int COPY[55][55];
// 지금 시간 바이러스맵
int NOW[55][55];
// 다음 시간 바이러스맵
int NEXT[55][55];
// 방문 표시
int visited[55][55];
// 끝난건지 비교
int markerNow[55][55];
int markerNext[55][55];
int used[15];
int answer;
// 병원
vector<Coord> h;
// 바이러스
vector<Coord> v;
// M개 조합 병원
vector<Coord> s;
int dr[] = { 0, 0, -1, 1 };
int dc[] = { -1, 1, 0, 0 };
int isClear(int MAP[55][55])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (MAP[i][j] == 0) return 0;
}
}
return 1;
}
int isChanged(int NOW[55][55], int NEXT[55][55])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (NEXT[i][j] != NOW[i][j])
return 1;
}
}
return 0;
}
void MapCopy(int A[55][55], int B[55][55])
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
A[i][j] = B[i][j];
}
}
}
void bfs(Coord h, int time)
{
int t = 0;
visited[h.row][h.col] = 1;
markerNext[h.row][h.col] = 1;
queue<Coord> nowQ;
nowQ.push(h);
while (!nowQ.empty())
{
Coord now = nowQ.front();
if (visited[now.row][now.col] > time)
{
nowQ.pop();
continue;
}
nowQ.pop();
for (int i = 0; i < 4; i++)
{
Coord n = { now.row + dr[i], now.col + dc[i] };
if (n.row < 0 || n.col < 0 || n.row >= N || n.col >= N) continue;
// if (NEXT[n.row][n.col] == 1 || NEXT[n.row][n.col] == 2) continue;
if (NEXT[n.row][n.col] == 1) continue;
if (visited[n.row][n.col] != 0) continue;
visited[n.row][n.col] = visited[now.row][now.col] + 1;
markerNext[n.row][n.col] = 1;
// 3은 청소한 바이러스 표시
if (NEXT[n.row][n.col] == 0) NEXT[n.row][n.col] = 3;
nowQ.push({ n.row, n.col });
}
}
}
int ClearVirus()
{
int time = 0;
MapCopy(NOW, COPY);
MapCopy(NEXT, NOW);
memset(markerNow, 0, sizeof(markerNow));
memset(markerNext, 0, sizeof(markerNext));
while (true)
{
if (time >= answer) return time;
// 고른 M개의 병원에서부터 청소
MapCopy(markerNow, markerNext);
for (int i = 0; i < s.size(); i++)
{
memset(visited, 0, sizeof(visited));
bfs(s[i], time);
}
// NOW와 NEXT가 같으면 끝
if (!isChanged(markerNow, markerNext) || isClear(NEXT)) break;
MapCopy(NOW, NEXT);
time++;
}
// 바이러스가 아직 존재하면
if (!isClear(NEXT))
time = 2134567890;
return time;
}
void dfs(int depth, int start)
{
if (depth == M)
{
MapCopy(COPY, MAP);
answer = min(answer, ClearVirus());
return;
}
for (int i = start; i < h.size(); i++)
{
if (used[i] == 1) continue;
used[i] = 1;
s.push_back(h[i]);
dfs(depth + 1, start + 1);
s.pop_back();
used[i] = 0;
}
}
void CLEAR()
{
answer = 2134567890;
memset(MAP, 0, sizeof(MAP));
memset(COPY, 0, sizeof(COPY));
memset(NOW, 0, sizeof(NOW));
memset(NEXT, 0, sizeof(NEXT));
}
void INPUT()
{
cin >> N >> M;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> MAP[i][j];
if (MAP[i][j] == 1)
{
v.push_back({ i, j });
}
if (MAP[i][j] == 2)
{
h.push_back({ i, j });
}
}
}
}
void SOLVE()
{
// M개 병원 고르기
dfs(0, 0);
if (answer == 2134567890)
{
cout << -1 << endl;
}
else
{
cout << answer << endl;
}
}
int main()
{
CLEAR();
INPUT();
SOLVE();
return 0;
}📌 memo 😊
1. 조합으로 뽑아낸 M개의 병원을 for문으로 돌아가면서 매번 bfs.
=> 모두 한 queue에 넣고 한번에 bfs 해도 됨.
=> BFS Queue에 넣을때는 "현재상태 ~ 다음상태"를 잘 정의할 것!
- 바이러스의 Clear를 결정할 때 현재 MAP과 다음 시간의 MAP을 비교함
=> 바이러스의 개수가 0일 때 바로 끝내자
=> 이 문제의 CRUX는 MAP의 범위가 크기때문에 바이러스의 개수가 많아졌을때 시간초과 우려가 있다는 것.
따라서, 최대한 MAP을 적게 탐색하도록 코드를 설계했어야 함!
공부방