[#15683] 감시

/* 백준 15683 감시 (200826) <시뮬> */

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n, m;
int ans = 100;  //나올 수 없는 최대수로 설정해놓기

//1번 카메라에는 각 방향이 있으므로 인자(dir)만 바꿔가면서 모든 카메라의 기본이 되도록
void camera1(vector<vector<int>>& board, int dir, int row, int col) {
	if (dir == 1) {
		//오른쪽으로
		for (int i = col+1; i < m; i++) {
			if (board[row][i] == 6)  //벽
				return;

			if (board[row][i] == 0)
				board[row][i] = -1;
		}
	}
	else if (dir == 2) {
		//아래로
		for (int i = row + 1; i < n; i++) {
			if (board[i][col] == 6)  //벽
				return;

			if (board[i][col] == 0)
				board[i][col] = -1;
		}
	}
	else if (dir == 3) {
		//왼쪽으로
		for (int i = col - 1; i >= 0; i--) {
			if (board[row][i] == 6)  //벽
				return;

			if (board[row][i] == 0)
				board[row][i] = -1;
		}
	}
	else {
		//위쪽으로
		for (int i = row - 1; i >= 0; i--) {
			if (board[i][col] == 6)  //벽
				return;

			if (board[i][col] == 0)
				board[i][col] = -1;
		}
	}
}

void camera2(vector<vector<int>>& board, int dir, int row, int col) {
	if (dir == 1) {
		//양옆으로
		camera1(board, 1, row, col);
		camera1(board, 3, row, col);
	}
	else if (dir == 2) {
		//위아래로
		camera1(board, 2, row, col);
		camera1(board, 4, row, col);
	}
}

void camera3(vector<vector<int>>& board, int dir, int row, int col) {
	if (dir == 1) {
		//오른쪽, 위
		camera1(board, 1, row, col);
		camera1(board, 4, row, col);
	}
	else if (dir == 2) {
		//오른쪽, 아래
		camera1(board, 1, row, col);
		camera1(board, 2, row, col);
	}
	else if (dir == 3) {
		//왼쪽, 아래
		camera1(board, 3, row, col);
		camera1(board, 2, row, col);
	}
	else if (dir == 4) {
		//왼쪽, 위
		camera1(board, 3, row, col);
		camera1(board, 4, row, col);
	}
}

void camera4(vector<vector<int>>& board, int dir, int row, int col) {
	if (dir == 1) {
		//왼, 위, 오
		camera1(board, 1, row, col);
		camera1(board, 3, row, col);
		camera1(board, 4, row, col);
	}
	else if (dir == 2) {
		//위, 오, 아
		camera1(board, 1, row, col);
		camera1(board, 2, row, col);
		camera1(board, 4, row, col);
	}
	else if (dir == 3) {
		//왼, 오, 아
		camera1(board, 3, row, col);
		camera1(board, 2, row, col);
		camera1(board, 1, row, col);
	}
	else if (dir == 4) {
		//왼, 위, 아
		camera1(board, 2, row, col);
		camera1(board, 3, row, col);
		camera1(board, 4, row, col);
	}
}

void camera5(vector<vector<int>>& board, int row, int col) {
	camera1(board, 1, row, col);
	camera1(board, 2, row, col);
	camera1(board, 3, row, col);
	camera1(board, 4, row, col);
}

void recursive(int totalCamera, vector<vector<int>>& board, int row, int col) {
	//Base case
	if (totalCamera == 0) {
		//모든 카메라 다 봤을때
		int temp = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (board[i][j] == 0)
					temp++;
			}
		}
		ans = min(ans, temp);

		return;
	}

	//한 row 중간에서 재귀로 넘어왔다면 다음 col부터 보고 다음 row에서 0번째 col부터 봐야 함
	//처음 for문 도는거면 col+1부터 돌아야하므로 처음 돈 건지 표시하는 flag 변수
	int isFirst = true;  
	for (int i = row; i < n; i++) {
		for (int j = 0; j < m; j++) {

			//처음이라면
			if (isFirst) {
				j = col + 1;  //다음 col부터
				isFirst = false;
				if (j == m)  //범위 넘는다면 다시 for문 선언으로 (row = 다음 row, col = 0 이 됨)
					continue;
			}

			if (board[i][j] >= 1 && board[i][j] <= 5) {
				//카메라라면
				int cameraNum = board[i][j];

				if (cameraNum == 1) {  //1번 카메라
					for (int dir = 1; dir <= 4; dir++) {
						vector<vector<int>> tempBoard = board;
						camera1(board, dir, i, j);
						recursive(totalCamera-1, board, i, j);
						board = tempBoard;  //되돌리기
					}
				}

				if (cameraNum == 2) {   //2번 카메라
					for (int dir = 1; dir <= 2; dir++) {
						vector<vector<int>> tempBoard = board;
						camera2(board, dir, i, j);
						recursive(totalCamera-1, board, i, j);
						board = tempBoard;  //되돌리기
					}
				}

				if (cameraNum == 3) {   //3번 카메라
					for (int dir = 1; dir <= 4; dir++) {
						vector<vector<int>> tempBoard = board;
						camera3(board, dir, i, j);
						//printBoard(board);
						recursive(totalCamera-1, board, i, j);
						board = tempBoard;  //되돌리기
					}
				}
				
				if (cameraNum == 4) {   //4번 카메라
					for (int dir = 1; dir <= 4; dir++) {
						vector<vector<int>> tempBoard = board;
						camera4(board, dir, i, j);
						recursive(totalCamera-1, board, i, j);
						board = tempBoard;  //되돌리기
					}
				}

				if (cameraNum == 5) {
					vector<vector<int>> tempBoard = board;
					camera5(board, i, j);
					recursive(totalCamera-1, board, i, j);
					board = tempBoard;  //되돌리기
				}
			}
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);

	vector<vector<int>> board(n, vector<int>(m));
	int totalCamera = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			scanf("%d", &board[i][j]);

			if (board[i][j] >= 1 && board[i][j] <= 5) {
				totalCamera++;
			}
		}
	}

	recursive(totalCamera, board, 0, 0);  //(0, 0)부터 시작  
	
	printf("%d", ans);

	return 0;
}

재귀를 이용한 완전 탐색 문제

 

1. 실수했던 부분

1) 재귀 호출할때 totalCamera-1이 아닌 totalCamera--를 해버림
    =>인자로 넘어가는 totalCamera만 1씩 줄여야하는데 --를 하면 그 자체에서 1씩 줄어든다.

2) 재귀 함수 안에서 이중 for문을 돌 때 j=col+1로 해버림
    => row가 바뀐다면 col은 처음부터(0부터) 봐야되는데 row가 바껴도 col+1번째부터 보는 문제 발생
    => for문을 처음 도는지를 알려주는 boolean 타입 변수를 하나 설정한 후, 처음돌때만 col+1로 해준다.

2. 재귀 함수

** 필수
1) 기저사례: 남은게 0일때 or 길이가 0일때 or ....
2) 재귀 호출 후 그 전 상태로 되돌려주기 (이 문제에서는 board = tempBoard 이 부분)