글 읽기 - 반례를 못찾겠습니다.

smiley_bin 4년 전 0

시작하자마자 틀렸습니다가 뜹니다.

제가 확인 못한 부분이 있을까요?

풀이는 DFS로 하였고 전 값 tmp에 저장하고 move를 통해서 map에서 cctv의 방향과 종류대로 -1를 넣어주었고 cnt가 cctv 개수와 같을 때 사각지대를 세고 원래 map을 tmp에서 가져와 전값으로 바꾸어 주는 형태로 짰습니다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int N, M;
int map[8][8];
vector<pair<int,pair<int, int> > > tv_loc;
int min_result = 100; //정답 

void move(int lotate, int x, int y) {
	switch (lotate) {
	case 0: //서쪽
		for (int i = y - 1;i >= 0;i--) {
			if (map[x][i] >0) break;
			if (map[x][i] == 0) map[x][i] = -1; 
		}
		break;
	case 1://북쪽
		for (int i = x-1;i>=0;i--) {
			if (map[i][y] >0) break;
			if (map[i][y] == 0) map[i][y] = -1;
		}
		break;
	case 2: //동쪽
		for (int i = y + 1;i<M;i++) {
				if (map[x][i] >0) break;
				if (map[x][i] == 0) map[x][i] = -1;
			}
		break;
	case 3: //남쪽
		for (int i = x + 1;i < N;i++) {
			if (map[i][y] >0) break;
			if (map[i][y] == 0) map[i][y] = -1;
		}
	}
}


int result() { //사각지대 구하기
	int min_cnt = 0;
	for (int i = 0;i < N;i++) {
		for (int j = 0;j < M;j++) {
			if (map[i][j] == 0) {
				min_cnt++;
			}
		}
	}
	return min_cnt;
}

void sol(int cnt) {
	if (cnt == tv_loc.size()) { //cnt==cctv 개수면 
		min_result = min(min_result, result());
		return;
	}

	int tmp[8][8]; //save prev data

	for (int i = 0;i < N;i++) {
		for (int j = 0;j < M;j++) {
			tmp[i][j] = map[i][j];
		}
	}
	
	int cctv_no = tv_loc[cnt].first; //cctv 종류 
	int x = tv_loc[cnt].second.first; //x,y 좌표
	int y = tv_loc[cnt].second.second;

	if (cctv_no == 1) {
		for (int i = 0;i < 4;i++) { //1번은 4방향
			move(i, x, y);
			sol(cnt + 1);
			for (int k = 0;k < N;k++) {//전 값으로 바꾸기
				for (int l = 0;l < M;l++) {
					map[k][l] = tmp[k][l];
				}
			}
		}
	}
	else if (cctv_no == 2) { //2번은 2방향만
		for (int i = 0;i < 2;i++) {
			move(i, x, y);
			move(i + 2, x, y);
			sol(cnt + 1);
			for (int k = 0;k < N;k++) {//전 값으로 바꾸기
				for (int l = 0;l < M;l++) {
					map[k][l] = tmp[k][l];
				}
			}
		}
	}
	else if (cctv_no == 3) { //3번은 4방향 전부 다
		for (int i = 1;i < 5;i++) {
			move(i%4, x, y);
			move((i + 1) % 4, x, y);
			sol(cnt + 1);
			for (int k = 0;k < N;k++) { //전 값으로 바꾸기
				for (int l = 0;l < M;l++) {
					map[k][l] = tmp[k][l];
				}
			}
		}
	}
	else if (cctv_no == 4) { //4번은 4방향 전부다
		for (int i = 0;i < 4;i++) {
			move(i, x, y);
			move((i + 1) % 4, x, y);
			move((i + 2) % 4, x, y);
			sol(cnt + 1);
			for (int k = 0;k < N;k++) {//전 값으로 바꾸기
				for (int l = 0;l < M;l++) {
					map[k][l] = tmp[k][l];
				}
			}
		}
	}
	else if (cctv_no == 5) { //5는 전방향 
		move(0, x, y);
		move(1, x, y);
		move(2, x, y);
		move(3, x, y);
		sol(cnt + 1);
	}
	
}

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] > 0 && map[i][j] < 6) tv_loc.push_back({ map[i][j],{ i,j } }); //cctv 종류와 맵 좌표
		}
	}

	if (tv_loc.size() == 0) { //cctv없는경우
		cout << result();
		return 0;
	}

	sol(0);
	cout << min_result;
	return 0;
}

wjdrhdms002 4년 전 0

move함수 조건인 if (map[x][i] >0) break;

이부분에서 cctv가 중복되어도 통과 되는 조건이 있어요

map[x][i] == 6, 즉 벽일때만 통과 못하도록 하면 될 것 같네요

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

문제

문제

출처

ICPC

반례를 못찾겠습니다.

smiley_bin 4년 전 0

wjdrhdms002 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말