백준 알고리즘 15683_감시 c++

문제

(링크)15683번: 감시 (acmicpc.net)

15683번: 감시

 

사고과정

문제 자체는 그리 어렵진 않았지만 예기치 못한 오류 때문에 시간을 많이 썼다. 처음엔 완전탐색을 하고싶지 않아서 답을 도출하는 망법을 생각했다. cctv가 각 방향을 탐색할 때 최대한 많은 구역을 탐색하면서 다음 cctv로 넘어가는 것인데, 아니나 다를까 예외적인 상황이 생겨서 오답처리 되었다. 그래서 결국 재귀함수를 이용하여 전체를 탐색하기로했다. 

내가 c++ vector를 사용하는 이유 중에는 재귀 함수를 사용할 때, 굳이 초기정보를 담은 map을 저장하고 불러가며 사용하지 않아도 되기 때문이다. int 배열을 함수에 넣을 땐 주소에 있는 값을 바꿀 수밖에 없지만, vector는 레퍼런스의 사용여부에 따라 변수처럼 지정할 수 있기 때문이다. 그런데 이 문제는 cctv의 종류에 따라 다르게 반복탐색해야하기 때문에 map을 백업하는 코드를 지정해두었다.

cctv위 위치를 저장 -> cctv의 상태에 따라 방향을 바꿔가며 map 갱신 -> 마지막에 사각지대 개수 갱신   

 

내코드

#include <iostream>
#include <vector>
#include <stack>
#define CHECK 7

using namespace std;

int height, width, answer = 100;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int state_num[5] = { 4,2,4,4,1 };

void copy(vector<vector<int>> a, vector<vector<int>>& b) {
	for (int i = 0; i < height; i++) {
		for (int j = 0; j < width; j++) {			//a->b
			b[i][j] = a[i][j];
		}
	}
}

void update(int dir, vector<vector<int>>& map,int x,int y) {
	dir %= 4;
	int X = x + dx[dir];
	int Y = y + dy[dir];
	while (X >= 0 && X < width && Y >= 0 && Y < height) {
		if (map[Y][X] == 6)break;

		if (map[Y][X] == 0)map[Y][X] = CHECK;
		Y += dy[dir];
		X += dx[dir];
	}
}

void Check(vector<vector<int>> map, stack<pair<int, int>> s) {
	if (s.empty()) {
		int count = 0;
		for (int i = 0; i < height; i++) {
			for (int j = 0; j < width; j++) {
				if (map[i][j] == 0)count++;
			}
		}
		if (answer > count)answer = count;
		return;
	}


	int x = s.top().second;
	int y = s.top().first;
	int state = map[y][x];
	s.pop();

	vector<vector<int>> copiedmap(height, vector<int>(width));

	for (int dir = 0; dir < state_num[state-1]; dir++) {

		copy(map, copiedmap);

		if (state == 1) {
			update(dir, map, x, y);
		}
		else if (state == 2) {
			update(dir, map, x, y);
			update(dir + 2, map, x, y);
		}
		else if (state == 3) {
			update(dir, map, x, y);
			update(dir + 1, map, x, y);
		}
		else if (state == 4) {
			update(dir, map, x, y);
			update(dir + 1, map, x, y);
			update(dir + 2, map, x, y);
		}
		else if (state == 5) {
			update(dir, map, x, y);
			update(dir + 1, map, x, y);
			update(dir + 2, map, x, y);
			update(dir + 3, map, x, y);
		}

		Check(map, s);
		copy(copiedmap, map);
	}


}



int main() {
	int i, j;
	cin >> height >> width;
	vector<vector<int>> map (height, vector<int>(width, 0));
	stack<pair<int, int>> S;
	for (i = 0; i < height; i++) {
		for (j = 0; j < width; j++) {
			cin >> map[i][j];
			if (map[i][j] > 0 && map[i][j] < 6) {
				S.push(make_pair(i, j));
			}
		}
	}

	Check(map, S);
	cout << answer;


	return 0;
}

먼저 stack에 cctv의 위치를 저장한다. 이후 map과 stack을 인자로한 함수를 사용하여 사각지대의 개수를 구한다. Check함수는 stack이 비면(모든 cctv의 경우를 탐색하면) 해당 map을 탐색하여 0으로 남아있는 사각지대의 개수를 갱신한다. 그 전엔 각 cctv의 상태(state)에 따라 반복횟수를 달리해가며 각 방향을 update한다. update함수는 인자로 받아온 방향(dir)으로 벽을 만나거나 map이 끝날 때까지 map을 CHECK로 갱신한다. 각 update를 진행하기 전엔 map을 copiedmap에 저장해 두어야한다. update를 전후로 map을 저장,불러오기를 반복하지 않으면 모든 방향을 탐색한 것처럼 처리되기 때문이다. 

 

피드백

효율적인 방법을 찾아보고싶어서 초반에 삽질을 좀 많이했고, 이후 map 저장/불러오기 때문에 시간을 많이 버렸다. 바보짓 안하기.