Python과 C++로 풀었으며 C++에서는 queue나 vector를 사용하는 경우가 있습니다.
https://www.acmicpc.net/problem/14502
이 문제의 핵심 포인트는 벽을 무조건 3개만 세운다는 점입니다.
3개를 세웠을 때의 안전영역의 최대가 되는 경우는 곧 바이러스가 가장 적게 퍼지는 경우를 뜻합니다.
2차원 배열의 0(빈 칸) 중 어디에 벽 3개를 세웠을때 바이러스가 가장 적게 퍼지는가를 묻고 있으므로, 모든 경우의 수를 조합으로 전부 따져서 최소값을 구하는 브루트 포스 방법으로 풀어보도록 하겠습니다.
- 벽 3개를 치는 경우의 수를 파악한다.
- 벽을 쳤을때 바이러스를 퍼트린다.
- 바이러스가 퍼진 양으로 답을 갱신한다.
3가지의 단계가 있고, 최대 8*8 배열이므로 브루트포스+백트래킹으로 풀어도 시간초과가 나지는 않겠지만 만약 배열 크기가 크거나 조건이 더 붙는 경우에는 다른 방법을 생각해야겠습니다.
C++
전체 코드입니다.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int ans = 0;
vector <pair<int, int>> temp;
int n, m;
int min_virus = 64;
vector <pair <int, int>> viruses;
vector <pair<int, int>> safe_zones;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
void spread_virus(char maps[8][8]) {
bool v_visited[8][8] = {false,};
for (int i = 0; i < 3; i++) {
maps[temp[i].first][temp[i].second] = '1';
}
int virus_count = 0;
queue <pair <int, int> > q;
int t = 0;
while (t < viruses.size()) {
q.push(viruses[t]);
v_visited[viruses[t].first][viruses[t].second] = true;
t++;
}
while (q.size() > 0) {
int x = q.front().first;
int y = q.front().second;
for (int k = 0; k < 4; k++) {
if (0 <= x + dx[k] && x + dx[k] < n && 0 <= y + dy[k] && y + dy[k] < m) {
if (maps[x+dx[k]][y+dy[k]] == '0' && v_visited[x+dx[k]][y+dy[k]] == false) {
v_visited[x+dx[k]][y+dy[k]] = true;
virus_count++;
q.push(make_pair(x + dx[k], y+dy[k]));
}
}
}
q.pop();
}
if (min_virus >= virus_count){
min_virus = virus_count;
}
for (int i = 0; i < 3; i++) {
maps[temp[i].first][temp[i].second] = '0';
}
return;
}
void comb(int k, int start, vector <pair<int, int>> safe_zones, char maps[8][8]) {
if (k == 3) {
spread_virus(maps);
return;
} else {
for (int i = start; i < safe_zones.size(); i++) {
temp.push_back(safe_zones[i]);
comb(k+1, i+1, safe_zones, maps);
temp.pop_back();
}
}
}
int main(){
cin >> n >> m;
char maps[8][8];
char t;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> t;
if (t == '0') {
safe_zones.push_back(make_pair(i, j));
} else if (t == '2') {
viruses.push_back(make_pair(i, j));
}
maps[i][j] = t;
}
}
comb(0, 0, safe_zones, maps);
cout << safe_zones.size() - min_virus - 3 << endl;
return 0;
}
쪼개서 보겠습니다.
전역변수와 초기 선언입니다.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int ans = 0; // 정답을 저장하고 출력하기 위한 변수 ans
vector <pair<int, int>> temp; // 조합을 짤 때 필요한 배열 temp
int n, m; // 크기를 입력받을 변수
int min_virus = 64; // 바이러스는 최대 64개
vector <pair <int, int>> viruses; // 바이러스 위치를 저장
vector <pair<int, int>> safe_zones; // 안전영역 위치를 저장
int dx[4] = {-1, 0, 1, 0}; // 방향 탐색을 위한 배열 dx
int dy[4] = {0, -1, 0, 1}; // 방향 탐색을 위한 배열 dymain 함수에서 입력을 받고, 바이러스의 위치와 안전 영역의 위치를 배열에 추가해주도록 하겠습니다.
지도는 2차원 배열로, 바이러스와 안전영역의 위치는 전역 위치에 존재하는 vector에 저장합니다.
int main(){
cin >> n >> m;
char maps[8][8]; // 지도를 저장하기 위한 2차원 배열
char t;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> t;
if (t == '0') {
safe_zones.push_back(make_pair(i, j)); // 안전 영역의 위치 저장
} else if (t == '2') {
viruses.push_back(make_pair(i, j)); // 바이러스의 위치 저장
}
maps[i][j] = t; // 지도에 저장
}
}
}이제 안전영역 중에서 벽을 칠 3개를 고르는 조합 함수와 바이러스를 퍼트리는 함수를 짜겠습니다.
void comb(int k, int start, vector <pair<int, int>> safe_zones, char maps[8][8]) {
if (k == 3) { // 조합 완성
spread_virus(maps); // 바이러스 퍼트릴 함수 실행
return;
} else {
for (int i = start; i < safe_zones.size(); i++) {
temp.push_back(safe_zones[i]);
comb(k+1, i+1, safe_zones, maps);
temp.pop_back();
}
}
}void spread_virus(char maps[8][8]) {
bool v_visited[8][8] = {false,}; // bfs에서 방문을 기록할 visited 배열을 모두 false로 초기화합니다.
for (int i = 0; i < 3; i++) { // 벽을 칠 안전영역에 모두 벽을 칩니다.
maps[temp[i].first][temp[i].second] = '1';
}
int virus_count = 0; // 바이러스가 퍼지는
queue <pair <int, int> > q; // bfs를 실행하기 위한 queue입니다.
int t = 0;
while (t < viruses.size()) { // 기존에 바이러스가 있는 위치의 visited를 전부 true로 바꿔주고 queue에 push합니다.
q.push(viruses[t]);
v_visited[viruses[t].first][viruses[t].second] = true;
t++;
}
while (q.size() > 0) { // bfs를 실행합니다.
int x = q.front().first;
int y = q.front().second;
for (int k = 0; k < 4; k++) {
if (0 <= x + dx[k] && x + dx[k] < n && 0 <= y + dy[k] && y + dy[k] < m) {
// bfs 탐색이 maps의 영역을 벗어나지 않도록 합니다.
if (maps[x+dx[k]][y+dy[k]] == '0' && v_visited[x+dx[k]][y+dy[k]] == false) { // 바이러스가 퍼질 수 있는 공간이며, 아직 한번도 퍼지지 않은 곳인지 검사합니다.
v_visited[x+dx[k]][y+dy[k]] = true; // 조건을 모두 만족하면 방문은 true
virus_count++; // 퍼지는 바이러스의 크기를 1 증가시킵니다.
q.push(make_pair(x + dx[k], y+dy[k])); // q에 push합니다.
}
}
}
q.pop();
}
if (min_virus >= virus_count){ // 답이 될 바이러스 갯수보다 현재 퍼진 바이러스의 갯수가 더 적으면
min_virus = virus_count; // 답은 현재 퍼진 바이러스의 갯수로 바꿔줍니다.
}
for (int i = 0; i < 3; i++) { // 다음 벽 위치에 벽을 치기 위해 쳤던 벽을 다시 해제합니다.
maps[temp[i].first][temp[i].second] = '0';
}
return;
}안전 영역의 크기에서 최소로 바이러스가 퍼지는 갯수를 빼준 뒤, 새로 친 벽의 갯수 3개까지 빼주면 답이 됩니다.
comb(0, 0, safe_zones, maps);
cout << safe_zones.size() - min_virus - 3 << endl;Python
예전에 짰던 파이썬도 코드는 비슷합니다. 함수와 구조의 차이가 조금 있지만 위와 개념과 작동방식은 거의 같습니다.
def spread_virus(temp):
global min_virus
v_visited = [[False] * m for _ in range(n)]
virus_count = 0
for vi in range(len(viruses)):
v_x, v_y = viruses[vi][0], viruses[vi][1]
v_visited[v_x][v_y] = True
q = [[v_x, v_y]]
while q:
x, y = q[0][0], q[0][1]
for k in range(len(dx)):
if 0 <= x + dx[k] < n and 0 <= y + dy[k] < m:
if maps[x+dx[k]][y+dy[k]] == 0 and v_visited[x+dx[k]][y+dy[k]] == False and [x+dx[k], y+dy[k]] not in temp:
v_visited[x+dx[k]][y+dy[k]] = True
q.append([x+dx[k], y+dy[k]])
virus_count += 1
q.pop(0)
min_virus = min(min_virus, virus_count)
return
def comb(k, start):
if k == 3:
spread_virus(temp)
return
for i in range(start, len(safe_zones)):
temp.append(safe_zones[i])
comb(k+1, i+1)
temp.pop()
n, m = map(int, input().split())
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
maps = [list(map(int, input().split())) for _ in range(n)]
viruses = []
safe_zones = []
for i in range(n):
for j in range(m):
if maps[i][j] == 0:
safe_zones.append([i, j])
elif maps[i][j] == 2:
viruses.append([i, j])
min_virus = 64
temp = []
comb(0, 0)
print(len(safe_zones) - min_virus - 3)느낀 점
브루트 포스로 문제를 풀었고 실행시간도 그리 길지는 않았지만 다른 좋은 방법이 있는지 생각해봐야겠습니다.
안녕하세요!