15683 감시

1. 문제

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

15683번: 감시

 

2. 코드

#include "pch.h"
#include <iostream>
#include <queue>

using namespace std;
int n, m;
int map[8][8];
vector<pair<int, int>> v;
int head[5] = { 0,4,2,4,4 };

int vsize = 0;
int mini = 987654321;

void find(int cctv, int h, int x, int y);
void dfs(int depth);
void fourDir(int d, int x, int y);

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] >= 1 && map[i][j] <= 4)
				v.push_back(make_pair(i, j));
		}
	}

	vsize = v.size();

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 5) {
				fourDir(0, i, j);
				fourDir(1, i, j);
				fourDir(2, i, j);
				fourDir(3, i, j);
			}
		}
	}
	dfs(0);
	cout << mini;
}

void dfs(int depth) {

	if (depth == vsize) {
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 0)
					cnt++;
			}
		}
		mini = min(mini, cnt);
		return;
	}

	int x = v[depth].first;
	int y = v[depth].second;
	int cctv = map[x][y];

	//map을 amap으로 복사
	int amap[8][8];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			amap[i][j] = map[i][j];
		}
	}

	for (int i = 0; i < head[cctv]; i++) {
		find(cctv, i, x, y);
		dfs(depth + 1);

		//cmap 초기화
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				map[i][j] = amap[i][j];
			}
		}
	}
}

void find(int cctv, int h, int x, int y) {
	if (h == 0) {
		fourDir(0, x, y);
		if (cctv == 3 || cctv == 4)
			fourDir(1, x, y);
		if (cctv == 2 || cctv == 4)
			fourDir(2, x, y);
	}
	else if (h == 1) {
		fourDir(1, x, y);
		if (cctv == 3 || cctv == 4)
			fourDir(2, x, y);
		if (cctv == 2 || cctv == 4)
			fourDir(3, x, y);
	}
	else if (h == 2) {
		fourDir(2, x, y);
		if (cctv == 3 || cctv == 4)
			fourDir(3, x, y);
		if (cctv == 4)
			fourDir(0, x, y);
	}
	else if (h == 3) {
		fourDir(3, x, y);
		if (cctv == 3 || cctv == 4)
			fourDir(0, x, y);
		if (cctv == 4)
			fourDir(1, x, y);
	}
}

void fourDir(int d, int x, int y) {
	//우
	if (d == 0) {
		for (int j = y + 1; j < m; j++) {
			if (map[x][j] == 6)
				break;
			if (map[x][j] == 0)
				map[x][j] = -1;
		}
	}
	//상
	else if (d == 1) {
		for (int i = x - 1; i >= 0; i--) {
			if (map[i][y] == 6)
				break;
			if (map[i][y] == 0)
				map[i][y] = -1;
		}
	}
	//좌
	else if (d == 2) {
		for (int j = y - 1; j >= 0; j--) {
			if (map[x][j] == 6)
				break;
			if (map[x][j] == 0)
				map[x][j] = -1;
		}
	}
	//하
	else if (d == 3) {
		for (int i = x + 1; i < n; i++) {
			if (map[i][y] == 6)
				break;
			if (map[i][y] == 0)
				map[i][y] = -1;
		}
	}
}

 

3. 후기

이 문제는 우선 경우의 수가 총 몇번이 나오는지 계산해야했다. 그래서 head라는 배열에 각 cctv마다 몇 번 회전해봐야 하는지 기록해 두었다. 5번 cctv는 회전해도 같으므로 미리 배열을 -1로 채워주고 1~4번 cctv만 dfs라는 함수에 넣어 재귀 형식으로 모든 경우의 수만큼 회전하도록 하였다. 

fourDir는 단순히 상,하,좌,우 원하는 방향으로 벽을 만나기 전까지 -1로 채워주는 함수이고, find에서 cctv의 번호와 몇번째 회전인지를 따져서 알맞은 방향으로 -1를 채워 넣어준다.