백준 알고리즘 14502_ 연구소 c++

문제

(링크) 14502번: 연구소 (acmicpc.net)

 

사고과정

이 문제는 정답률에서 볼 수 있듯 그리 어려운 문제는 아니다. 처음 문제를 봤을 때 생각했던 것은 어떻게 하면 효율적으로 코드를 짤 수 있을까였다. 그래서 생각보다 문제를 푸는데 오래 걸렸다. 원래는 C만 이용해서 풀려고 했는데 map 배열을 각 단계에서 수정하지 않고 사용하고 싶어서 c++의 이중 vector를 사용하기로 했다. 

 

문제를 푸는데 3가지 단계로 분할했다.

1. 문제에서 벽을 꼭 3개 설치한다 했으니, 아무 것도 없는 공간 중 3개의 벽을 임의로 고른다

2. 벽을 세운 후 바이러스를 퍼뜨린다.

3. 바이러스가 모두 퍼진 후 안전구역의 칸을 구한다.

이 중 가장 생각을 많이 한 것은 첫 번째 단계이다. 육안으로 볼 땐 대충 어디에 벽을 세워야할 지 감이오지만, 코드로는 그 부분을 알 수 없고, 어차피 최댓값을 구해야 하기 때문에 결국 전체를 탐색하기로 하였다. 

 

내 코드

 

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

//
//
//
//int CountSafe(vector<vector<int>> map,int height,int width) {
//	int count = 0;
//	for (int i = 0; i < height; i++) {
//		for (int j = 0; j < width; j++) {
//			if (map[i][j] == 0)count++;
//		}
//	}
//	return count;
//}
int SpreadVirus(vector<vector<int>> map,int height,int width,stack<pair<int,int>> virus) {
	int dx[4] = { 0,0,1,-1 };
	int dy[4] = { 1,-1,0,0 };
	int virusNum = 0;
	while(!virus.empty()) {
		int x = virus.top().second;
		int y = virus.top().first;

		virus.pop();
		for (int i = 0; i < 4; i++) {
			int X = x + dx[i];
			int Y = y + dy[i];
			if (X >= 0 && X < width && Y >= 0 && Y < height) {
				if (map[Y][X] == 0) {
					map[Y][X] = 2;
					virus.push(make_pair(Y, X));
					virusNum++;
				}
			}
		}
	}
	//return CountSafe(map, height, width);
	return virusNum;
}
int BuildWall(vector<vector<int>> map,int height,int width,stack<pair<int,int>> virus,pair<int,int> Wall_1, pair<int, int> Wall_2, pair<int, int> Wall_3) {
	map[Wall_1.first][Wall_1.second] = 1;
	map[Wall_2.first][Wall_2.second] = 1;
	map[Wall_3.first][Wall_3.second] = 1;


	return SpreadVirus(map, height, width, virus);
}


int main() {
	int height, width, i, j;
	cin >> height >> width;

	vector<vector<int>> map(height, vector<int>(width,0));
	stack<pair<int,int>> Virus;
	vector<pair<int, int>> Wall;

	for (i = 0; i < height; i++) {
		for (j = 0; j < width; j++) {
			cin >> map[i][j];
			if (map[i][j] == 0) {
				Wall.push_back(make_pair(i, j));
			}
			else if (map[i][j] == 2) {
				Virus.push(make_pair(i, j));
			}
		}
	}

	int max = 0;
	for (i = 0; i < Wall.size() - 2; i++) {
		for (j = i + 1; j < Wall.size() - 1; j++) {
			for (int k = j+1; k < Wall.size(); k++) {
				int tmp = Wall.size()- BuildWall(map, height, width, Virus, Wall[i], Wall[j], Wall[k])-3;
				
				if (max < tmp)max = tmp;
			}
		}
	}


	cout << max;

	return 0;
}

코드의 흐름은 다음과 같다.

1. 문제조건대로 데이터 입력

2. vector을 이용해 map에 정보 저장

    -이때 map의 값에 따라 비어있는 공간을 wall vector에 저장, 바이러스를 virus stack에 push

3. 3중 for문을 이용해 Wall vector의 값 중 3개를 고른 뒤, BuildWall 함수에 넣어 '새로생긴 바이러스의 ' 개수를 구한다.

   //처음엔 <벽을 세운다 -> 바이러스를 퍼트린다 -> 안전지대의 개수를 구한다(초반 주석처리한 부분)> 순서로 답을         찾았으나, 92ms이 걸렸다.  시간을 줄이고 싶어 <처음 빈공간 - (새로생긴 바이러스 개수 + 새로생긴 벽의개수(3))>       의 값을 사용했다        

4. 위 값들 중 최댓값을 갱신하며 3번 과정을 반복한다

 

 

피드백

일단 시간복잡도를 줄이는 방법을 생각해보고 c언어만을 이용하는 법도 생각해봐야겠다. c++의 vector가 함수안에 들어가서 자기자신을 바꾸지 않는 점이 너무 편리해서 하기싫긴 하다.