15683 - 감시

안녕하세요. 꼬동입니다.

 

문제 푸는게 재밌네용.

 

옛날에 열심히 공부했던 생각도 많이 나고요. ㅋㅋ

 

그래서 한 번 더 풀어봤습니다.

 

삼성 SW 기출 문제의 정석 같은 문제 풀어봤는데, 조건만 잘 파악한다면, 그렇게 어려운 문제는 아니었던거 같습니다.

 

좀 더 깔끔하게 짤 수도 있었을 거 같은데, 뭐 풀면 장땡이죠 !

#include <stdio.h>

int N, M;

int cctvs[10][3]; // y, x, type
int cctvCnt;

int map[10][10];

int result;

void init() {
	scanf("%d %d", &N, &M);
	for (int n = 0; n < N; ++n) {
		for (int m = 0; m < M; ++m) {
			scanf("%d", &map[n][m]);
			if (1 <= map[n][m] && map[n][m] <= 5) {
				cctvs[cctvCnt][0] = n;
				cctvs[cctvCnt][1] = m;
				cctvs[cctvCnt++][2] = map[n][m];
			}
		}
	}
	result = 1e10;
}

int check() {
	int result = 0;
	for (int n = 0; n < N; ++n) {
		for (int m = 0; m < M; ++m) {
			if (map[n][m] == 0) result++;
		}
	}
	return result;
}

int dy[20] = { -1, 0, 1, 0, -1, 0, 1, 0, -1, 0, 1, 0, -1, 0, 1, 0, -1, 0, 1, 0 };
int dx[20] = { 0, 1, 0, -1, 0, 1, 0, -1, 0, 1, 0, -1, 0, 1, 0, -1, 0, 1, 0, -1 };

void draw(int y, int x, int dy, int dx, int dv) {
	while (true) {
		if (0 <= y + dy && y + dy < N && 0 <= x + dx && x + dx < M && map[y + dy][x + dx] != 6) {
			if (1 > map[y + dy][x + dx] || map[y + dy][x + dx] > 5) map[y + dy][x + dx] += dv;
			y += dy;
			x += dx;
		}
		else break;
	}
}

void search(int tv, int dir) {
	int y = cctvs[tv][0];
	int x = cctvs[tv][1];
	int type = cctvs[tv][2];

	if (type == 1) {
		draw(y, x, dy[dir], dx[dir], -1);
	}
	else if (type == 2) {
		draw(y, x, dy[dir], dx[dir], -1);
		draw(y, x, dy[dir + 2], dx[dir + 2], -1);
	}
	else if (type == 3) {
		draw(y, x, dy[dir], dx[dir], -1);
		draw(y, x, dy[dir + 1], dx[dir + 1], -1);
	}
	else if (type == 4) {
		draw(y, x, dy[dir], dx[dir], -1);
		draw(y, x, dy[dir + 1], dx[dir + 1], -1);
		draw(y, x, dy[dir + 3], dx[dir + 3], -1);
	}
	else if (type == 5) {
		draw(y, x, dy[dir], dx[dir], -1);
		draw(y, x, dy[dir + 1], dx[dir + 1], -1);
		draw(y, x, dy[dir + 2], dx[dir + 2], -1);
		draw(y, x, dy[dir + 3], dx[dir + 3], -1);
	}
}

void unsearch(int tv, int dir) {
	int y = cctvs[tv][0];
	int x = cctvs[tv][1];
	int type = cctvs[tv][2];

	if (type == 1) {
		draw(y, x, dy[dir], dx[dir], 1);
	}
	else if (type == 2) {
		draw(y, x, dy[dir], dx[dir], 1);
		draw(y, x, dy[dir + 2], dx[dir + 2], 1);
	}
	else if (type == 3) {
		draw(y, x, dy[dir], dx[dir], 1);
		draw(y, x, dy[dir + 1], dx[dir + 1], 1);
	}
	else if (type == 4) {
		draw(y, x, dy[dir], dx[dir], 1);
		draw(y, x, dy[dir + 1], dx[dir + 1], 1);
		draw(y, x, dy[dir + 3], dx[dir + 3], 1);
	}
	else if (type == 5) {
		draw(y, x, dy[dir], dx[dir], 1);
		draw(y, x, dy[dir + 1], dx[dir + 1], 1);
		draw(y, x, dy[dir + 2], dx[dir + 2], 1);
		draw(y, x, dy[dir + 3], dx[dir + 3], 1);
	}
}

// dir 0: 위, 1: 오, 2: 밑, 3: 왼
void dfs(int tv) {
	if (tv == cctvCnt - 1) {
		int val = check();
		if (result > val) {
			result = val;
		}
		return;
	}
	for (int i = 0; i < 4; ++i) {
		search(tv + 1, i);
		dfs(tv + 1);
		unsearch(tv + 1, i);
	}
}

int main(void) {
	init();

	dfs(-1);

	printf("%d", result);
	return 0;
}

 

---

ㅇ상sd 15683 - 감시였습니다. ^_^