백준 14502 연구소

eprj453·2020년 3월 20일
0

Python과 C++로 풀었으며 C++에서는 queue나 vector를 사용하는 경우가 있습니다.

https://www.acmicpc.net/problem/14502

이 문제의 핵심 포인트는 벽을 무조건 3개만 세운다는 점입니다.

3개를 세웠을 때의 안전영역의 최대가 되는 경우는 곧 바이러스가 가장 적게 퍼지는 경우를 뜻합니다.

2차원 배열의 0(빈 칸) 중 어디에 벽 3개를 세웠을때 바이러스가 가장 적게 퍼지는가를 묻고 있으므로, 모든 경우의 수를 조합으로 전부 따져서 최소값을 구하는 브루트 포스 방법으로 풀어보도록 하겠습니다.

  1. 벽 3개를 치는 경우의 수를 파악한다.
  2. 벽을 쳤을때 바이러스를 퍼트린다.
  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}; // 방향 탐색을 위한 배열 dy

main 함수에서 입력을 받고, 바이러스의 위치와 안전 영역의 위치를 배열에 추가해주도록 하겠습니다.

지도는 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)

느낀 점

브루트 포스로 문제를 풀었고 실행시간도 그리 길지는 않았지만 다른 좋은 방법이 있는지 생각해봐야겠습니다.

profile
안녕하세요!

0개의 댓글