[BOJ] 15683. 감시

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

15683번: 감시

 

배운점 :

barking dog 님의 풀이(4진법으로 풀기)는 굉장히 아름다운 풀이였다.

 

스스로 풀었는데, 난 백트래킹이라고 생각하는데 pruning이 없어서 그냥 완전탐색이다.

근데 난 머리속에

 

이 그림을 상상하며 풀었다. 이걸 손으로 구현하면 풀리겠다고 생각했다.

 

1. std::copy로 배열복사하는법 배웠다. (지정한 배열사이즈만큼 복사해야한다)

 

int board_copy[10][10];

copy(&board[0][0], &board[0][0] + 100, &board_copy[0][0]);

 

2. max에 list를 넘기는것도 되더라.

 

#include<bits/stdc++.h>
using namespace std;

int N,M; // N = ROW, M = COL
tuple<int, int,int> q[70];
int idx;
int searchPath(int x, int y, list<int> flag,int board[][10]) // 0 fix 1 temp
{
	int cnt = 0;

	for(int n : flag)
	{
		if(n == 1){
			// 우
			for(int i = y; i < M; i++)
			{
				if(board[x][i] == 6) break; //벽에 걸림
				else if(board[x][i] == 0){
					board[x][i] = -1; // 지나간경우
					cnt++;
					
				}
			}
		}else if(n == 2){
			// 좌
			for(int i = y; i >= 0; i--)
			{
				if(board[x][i] == 6) break; //벽에 걸림
				else if(board[x][i] == 0){
					board[x][i] = -1; // 지나간경우
					cnt++;
					
				}
			}
		}else if(n == 3){
			// 상
			for(int i = x; i >= 0; i--)
			{
				if(board[i][y] == 6) break; //벽에 걸림
				else if(board[i][y] == 0){
					board[i][y] = -1; // 지나간경우
					cnt++;
				}
			}
		}else{
			// 하
			for(int i = x; i < N; i++)
			{
				if(board[i][y] == 6) break; //벽에 걸림
				else if(board[i][y] == 0){
					board[i][y] = -1; // 지나간경우
					cnt++;
				}
			}
		}	
	}
	
	return cnt;
}

int backtrack(int board[][10],int k)
{
	if(k == idx) return 0;

	int cctv = get<0>(q[k]); // cctv
	int second = get<1>(q[k]); // x
	int third = get<2>(q[k]); // y
	int p,q,r,s;
	int board_copy[10][10];
	int board_copy2[10][10];
	int board_copy3[10][10];
	int board_copy4[10][10];
	copy(&board[0][0], &board[0][0] + 100, &board_copy[0][0]);
	copy(&board[0][0], &board[0][0] + 100, &board_copy3[0][0]);
	copy(&board[0][0], &board[0][0] + 100, &board_copy2[0][0]);
	copy(&board[0][0], &board[0][0] + 100, &board_copy4[0][0]);
	switch(cctv)
		{
			case 5 :
				return searchPath(second,third,{1,2,3,4},board_copy) + backtrack(board_copy, k+1);
				break;
			case 4 :
				p = searchPath(second,third,{1,2,3},board_copy) + backtrack(board_copy, k+1);
				q = searchPath(second,third,{1,3,4},board_copy2) + backtrack(board_copy2, k+1);
				r = searchPath(second,third,{1,2,4},board_copy3) + backtrack(board_copy3, k+1);
				s = searchPath(second,third,{2,3,4},board_copy4) + backtrack(board_copy4, k+1);
				
				return max({p,q,r,s});
				
				// 한번 더
				break;
			case 3 :
				p = searchPath(second,third,{1,3},board_copy) + backtrack(board_copy, k+1);
				q = searchPath(second,third,{1,4},board_copy2) + backtrack(board_copy2, k+1);
				r = searchPath(second,third,{2,4},board_copy3) + backtrack(board_copy3, k+1);
				s = searchPath(second,third,{2,3},board_copy4) + backtrack(board_copy4, k+1);
				
				return max({p,q,r,s});
				break;
			case 2 : 
				p = searchPath(second,third,{1,2},board_copy) + backtrack(board_copy, k+1);
				q = searchPath(second,third,{3,4},board_copy2) + backtrack(board_copy2, k+1);
				return max(p,q);
				
				break;
			case 1 :
				p = searchPath(second,third,{1},board_copy) + backtrack(board_copy, k+1);
				q = searchPath(second,third,{2},board_copy2) + backtrack(board_copy2, k+1);
				r = searchPath(second,third,{3},board_copy3) + backtrack(board_copy3, k+1);
				s = searchPath(second,third,{4},board_copy4) + backtrack(board_copy4, k+1);
				return max({p,q,r,s});
				
				break;
			default : 
				break;
		}
}
int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t = 0;
	int ret;
	
	int board[10][10];
	cin >> N >> M;
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < M; j++)
		{
			cin >> board[i][j];
			if(board[i][j] >= 1 && board[i][j] <= 5)
			{
				q[idx++] = {board[i][j],i,j};
			}else if(board[i][j] == 6){
				t++; // 벽돌
			}
		}
	}
	
	ret = backtrack(board,0);
	
	cout << N*M - idx - ret - t << "\n";


	return 0;
}

 

전체 숫자의 개수 - 벽돌 개수 - cctv 개수 - cctv가 감시하는 숫자 개수 로 답을 구했다.

 

거의 저녁 6시부터 해서 새벽까지 풀었다.

왜 오래걸렸는가?

 

1. 처음에는 greedy처럼 일단 cctv 숫자가 높은것부터 최대한 많이 보는 방식으로 해결하고자 했다.

실제로 테케가 좀 많이 맞았다. 근데 반례가 금방 나왔다. 이건 아니다 싶었다. 여기서 이미 한 2시간 버렸다.

 

2. 배열을 copy하지 않고 같은 배열을 쓰니까, call by ref라서 계속 값이 바뀐 배열들이 넘어가는게 문제였다.

 

배열을 계속 복사해서 시간이 오래걸릴 줄 알았는데, 의외로 그렇지 않았다.

copy의 time complexity가 Exactly (end - begin) assignments 라고 한다. 의외로 순식간이였다. (작아서 가능했던것 같다)

 

 

 

시간은 의외로 빨랐다.

 

머리 한 300개 뜯었다.

끝.