글 읽기 - 56% 까지 맞다가 틀려버립니다.

kgy94k 3년 전 0

CCTV로 감시 지역을 체크하기 전에, 해당 CCTV 방향이 테두리나 벽 공간에 막혀있는지 여부를 먼저 확인하는 코드를 'chck(int r, int c, int d)'로 추가하였습니다.

이 코드를 삽입하기 전에는 다 맞았는데, 위의 코드를 삽입하면 중간에 틀리게 됩니다.

게시판 모든 반례 대입했을 때 정답 제대로 나오고 제가 봤을때는 문제가 없어보이는데 잘못된 부분이 있는것 같습니다.

혹시 제가 놓친 부분이나 코드에 오류가 있다면 말씀해주시면 감사하겠습니다!!

#include <stdio.h>
#include <vector>

using namespace std;

int N, M;
int MAT[9][9];

vector <pair<int, int>> vec;

int dr[] = { 0, 1, 0, -1 };
int dc[] = { 1, 0, -1, 0 };

int ans;

void monitoring(int r, int c, int d, int org, int chg) { // 감시 지역 마킹
	while (true) {
		r = r + dr[d]; c = c + dc[d];
		if (r < 1 || r > N || c < 1 || c > M || MAT[r][c] == 6) {
			break;
		}
		if (MAT[r][c] == org) {
			MAT[r][c] = chg;
		}
	}
}

void opt(int r, int c, int d, int org, int chg) { // CCTV가 감시할 지역 마킹
	if (MAT[r][c] == 1) { // 1번 CCTV인 경우
		monitoring(r, c, d, org, chg);
	}
	else if (MAT[r][c] == 2) { // 2번 CCTV인 경우
		monitoring(r, c, d, org, chg);
		monitoring(r, c, (d + 2) % 4, org, chg);
	}
	else if (MAT[r][c] == 3) { // 3번 CCTV인 경우
		monitoring(r, c, d, org, chg);
		monitoring(r, c, (d + 1) % 4, org, chg);
	}
	else if (MAT[r][c] == 4) { // 4번 CCTV인 경우
		monitoring(r, c, d, org, chg);
		monitoring(r, c, (d + 1) % 4, org, chg);
		monitoring(r, c, (d + 3) % 4, org, chg);
	}
}

int chck(int r, int c, int d) { //감시 지역 유뮤 확인
	int nR = r + dr[d]; int nC = c + dc[d];
	int cannot = 0;
	if (nR < 1 || nR > N || nC < 1 || nC > M || MAT[nR][nC] == 6) {
		cannot = 1; 
	}
	return cannot; 
}

void dfs(int num){ //감시 지역 탐색!
	if (num == vec.size()) {
		int cnt = 0;
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (MAT[i][j] == 0) {
					cnt++;
				}
			}
		}
		if (ans > cnt) {
			ans = cnt;
		}
	}
	else {
		int r = vec[num].first; int c = vec[num].second;
		int cnt = 0;
		for (int i = 0; i < 4; i++) {
			int cannot = chck(r, c, i); // 해당 CCTV가 진행될 방향의 감시 가능 지역 유뮤 확인
			if (cannot == 1) { //만약 감시할 지역이 없으면 다른 방향 재확인
				cnt++;
				continue;
			}
			opt(r, c, i, 0, -(num + 1)); // n 번째 CCTV가 감시할 지역을 -(n+1)로 마킹
			dfs(num + 1);
			opt(r, c, i, -(num + 1), 0); //원상복귀
		}
		if (cnt == 4) { // 만약 4방향 모두 테두리나 벽으로 막혀있는 경우 n+1번째 cctv확인
			dfs(num + 1);
		}
	}
}

int main() {
	scanf("%d %d", &N, &M);
	vec.clear();
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf("%d", &MAT[i][j]);
			if (MAT[i][j] >= 1 && MAT[i][j] <= 5) {
				vec.push_back(make_pair(i, j)); // CCTV 위치 저장
			}
		}
	}
	int num_cctv = vec.size();
	for (int i = num_cctv - 1; i >= 0; i--) { //5번 타입 CCTV 유무 확인
		int x = vec[i].first; int y = vec[i].second;
		if (MAT[x][y] == 5) { //5번 타입의 CCTV 라면 감시지역을 -10으로 체크 
			for (int n = 0; n < 4; n++) {
				monitoring(x, y, n, 0, -10);
			}
			vec.erase(vec.begin() + i); //5번 타입 CCTV 위치 삭제
		}
	}
	ans = 64;
	dfs(0); // 감시지역 탐색
	printf("%d", ans);
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

56% 까지 맞다가 틀려버립니다.

kgy94k 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말