백준 15683 c++ "감시" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 구현 문제이다.

dx dy 를 이용하여 1번부터5번까지 경우의 수를 나눠서 진행방향으로 나아가야 된다.

 

필자는 처음에 복사하는 copyArr 을 전역변수로 선언하여 문제가 생겼다.

다음부터는 copyArr을 선언하는 변수는 지역 변수로 선언해야 될거 같다.

 

왜 전역변수로 선언하면 문제가 되냐면 예를들어 2번에서 순수한 arr을 복사시켜 놨는데

4번 idx로 dfs를 진행하면 copyArr을 4번에서의 순수한 arr을 또 복사시키게 된다.

이렇게 되면 2번 idx로 돌아왔을 때 기존 순수한 2번 arr이 복사가 되는게 아닌

다른 값이 복사가 되어져 있기 때문이다. 중요한 부분이다.

 

아래는 소스코드 상세 해설이다

 

 

• 전역 변수 및 기본 설정
  • Node라는 pair<int, int> 타입을 정의하여 좌표를 관리하고, dx1과 dy1 배열을 통해 이동 방향을 설정합니다. 각 방향은 {오른쪽, 위, 왼쪽, 아래} 순서로 지정됩니다.
  • arr는 맵을 저장하는 2차원 벡터이며, c_visited는 방문 여부를 저장하는 벡터입니다.
  • numberIdx 벡터는 특정 숫자가 있는 위치를 기록합니다.
  • resultMinCount는 최소의 볼 수 없는 영역을 계산하기 위한 변수이며, N과 M은 맵의 크기를 저장합니다.
• 입력 함수 (Input 함수)
  • 사용자로부터 맵의 크기 N과 M을 입력받고, arr와 c_visited를 초기화합니다.
  • 맵의 각 칸에 대한 정보를 입력받아, 만약 6이 아니고 0도 아닌 값이라면 해당 좌표를 numberIdx에 저장하고 c_visited에서 방문 불가로 표시합니다.
• 범위 체크 함수 (isInside 함수)
  • 현재 좌표가 맵 범위 안에 있는지 확인합니다. 이 함수는 true나 false를 반환하여 범위 외로 벗어나는지 검사합니다.
• 이동 함수 (goToMove 함수)
  • nowNode 위치에서 주어진 방향 (dx, dy)으로 이동합니다.
  • 벽(6)을 만나거나 맵 범위를 벗어나면 이동을 중단합니다. 만약 그 칸이 비어있는 칸(0)이라면, isMake 값에 따라 해당 칸을 -1로 채우거나 다시 0으로 돌려놓습니다.
• 감시 카메라 설정 함수 (setMoniter 함수)
  • 카메라 종류에 따라 감시 방향을 설정합니다. 카메라의 종류 num과 방향 i, 현재 위치 nowNode를 입력받아 설정합니다.
  • 예를 들어, num이 1인 경우 한 방향으로만 감시를 설정하고, num이 2인 경우 반대 방향을 포함해 두 방향을 감시합니다.
• 감시 카메라 제거 함수 (deleteMoniter 함수)
  • setMoniter와 동일한 구조로, 카메라의 감시 영역을 제거합니다. 주어진 위치에서 감시 중인 영역을 초기 상태로 복원합니다.
• 볼 수 없는 영역 계산 함수 (getDontSeeCount 함수)
  • 맵에서 볼 수 없는 영역(값이 0인 영역)의 개수를 셉니다.
  • 만약 현재 개수가 resultMinCount보다 작다면 resultMinCount를 갱신합니다.
• 조합 함수 (combination 함수)
  • 감시 카메라의 위치와 방향을 조합하여 모든 경우를 탐색합니다.
  • numberIdx에 저장된 감시 카메라의 모든 위치에 대해 각 방향을 설정해가며 combination 함수를 재귀적으로 호출합니다.
  • 설정 후 원래 맵으로 되돌리기 위해 copyMap에 맵을 복사하고 재설정합니다.
• 게임 시작 (GameStart 함수)
  • combination(0)을 호출하여 모든 감시 카메라의 조합을 탐색합니다.
  • 탐색 후 resultMinCount 값을 출력하여 볼 수 없는 최소 영역의 개수를 계산한 결과를 출력합니다.

 

 

 

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

//배열로 하나를 관리한다.
typedef pair<int, int> Node;
int dx1[4] = { 1,0,-1,0 };
int dy1[4] = { 0,-1,0,1 };

vector<vector<int>> arr;
vector<vector<bool>> c_visited;
vector<Node> numberIdx;

int resultMinCount = 1000000;
int N, M;

void Input() {
	cin >> N >> M;
	arr.resize(N);
	c_visited.resize(N);
	for (int i = 0; i < N; i++) {
		arr[i].resize(M);
		c_visited[i].resize(M, true);
	}

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			cin >> arr[i][k];

			if (arr[i][k] != 6 && arr[i][k] != 0) {
				numberIdx.push_back({ i,k });
				c_visited[i][k] = false;
			}
		}
	}
}

bool isInside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
	return false;
}

void goToMove(int dx, int dy, Node nowNode, bool isMake) {

	int nowSero = nowNode.first;
	int nowGaro = nowNode.second;

	while (1) {
		int nextSero = nowSero + dy;
		int nextGaro = nowGaro + dx;
		nowSero = nextSero;
		nowGaro = nextGaro;
		if (isInside(nextSero, nextGaro) == false)return;
		if (arr[nextSero][nextGaro] == 6)return;
		if (arr[nextSero][nextGaro] >= 1 && arr[nextSero][nextGaro] <= 5)continue;

		if (isMake == true)arr[nextSero][nextGaro] = -1;
		else if (isMake == false) arr[nextSero][nextGaro] = 0;

	}

}

void setMoniter(int num, int i, Node nowNode) {
	if (num == 1) {
		goToMove(dx1[i], dy1[i], nowNode, true);
	}
	else if (num == 2) {
		goToMove(dx1[i], dy1[i], nowNode, true);
		goToMove(dx1[(i + 2) % 4], dy1[(i + 2) % 4], nowNode, true);
	}
	else if (num == 3) {
		goToMove(dx1[i], dy1[i], nowNode, true);
		goToMove(dx1[(i + 1) % 4], dy1[(i + 1) % 4], nowNode, true);
	}
	else if (num == 4) {
		goToMove(dx1[(i + 3) % 4], dy1[(i + 3) % 4], nowNode, true);
		goToMove(dx1[i], dy1[i], nowNode, true);
		goToMove(dx1[(i + 1) % 4], dy1[(i + 1) % 4], nowNode, true);
	}
	else if (num == 5) {
		goToMove(dx1[(i + 3) % 4], dy1[(i + 3) % 4], nowNode, true);
		goToMove(dx1[i], dy1[i], nowNode, true);
		goToMove(dx1[(i + 1) % 4], dy1[(i + 1) % 4], nowNode, true);
		goToMove(dx1[(i + 2) % 4], dy1[(i + 2) % 4], nowNode, true);
	}
}
void deleteMoniter(int num, int i, Node nowNode) {
	if (num == 1) {
		goToMove(dx1[i], dy1[i], nowNode, false);
	}
	else if (num == 2) {
		goToMove(dx1[i], dy1[i], nowNode, false);
		goToMove(dx1[(i + 2) % 4], dy1[(i + 2) % 4], nowNode, false);
	}
	else if (num == 3) {
		goToMove(dx1[i], dy1[i], nowNode, false);
		goToMove(dx1[(i + 1) % 4], dy1[(i + 1) % 4], nowNode, false);
	}
	else if (num == 4) {
		goToMove(dx1[(i + 3) % 4], dy1[(i + 3) % 4], nowNode, false);
		goToMove(dx1[i], dy1[i], nowNode, false);
		goToMove(dx1[(i + 1) % 4], dy1[(i + 1) % 4], nowNode, false);
	}
	else if (num == 5) {
		goToMove(dx1[(i + 3) % 4], dy1[(i + 3) % 4], nowNode, false);
		goToMove(dx1[i], dy1[i], nowNode, false);
		goToMove(dx1[(i + 1) % 4], dy1[(i + 1) % 4], nowNode, false);
		goToMove(dx1[(i + 2) % 4], dy1[(i + 2) % 4], nowNode, false);
	}
}

void getDontSeeCount() {
	int count = 0;

	for (int i = 0; i < N; i++) {
		for (int k = 0; k < M; k++) {
			if (arr[i][k] == 0) {
				count++;
				continue;
			}


		}
	}

	if (resultMinCount > count) {

		resultMinCount = count;
		return;
	}
}

void combination(int startIdx) {

	if (startIdx == numberIdx.size()) {
		//arr은 -1로 도배

		getDontSeeCount();
		return;
	}

	int nowSero = numberIdx[startIdx].first;
	int nowGaro = numberIdx[startIdx].second;

	vector<vector<int>> copyMap;
	for (int i = 0; i < 4; i++) {
		copyMap = arr;

		setMoniter(arr[nowSero][nowGaro], i, { nowSero,nowGaro });
		combination(startIdx + 1);
		arr = copyMap;
	}
}


void GameStart() {
	combination(0);
	cout << resultMinCount;
}

int main(void) {
	Input();
	GameStart();
}