글 읽기 - 반례 및 오류가있을까요!?

lswoo3021 5년 전 1

안녕하세요... 기존에 풀었던 문제인데 방식을 바꾸어 풀어봤습니다.

코드가 오히려 더 깔끔하고 정답도 잘나와서 자신있었는데... 제출결과는 틀림이네요 ㅠ

TC및 게시판의 반례는 모두 검증해보았습니다... 혹시 찾으실 수 있다면 반례나 지적 부탁드리겠습니다.

* 로직은 bfs로 각 카메라 감시를 시행

* dfs로 카메라에 따라 모든 경우의 수를 반복

입니다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

#define MAX_SIZE 8


using namespace std;

int n, m;
int map[MAX_SIZE][MAX_SIZE];
vector <pair<int, int>> cam;
int dx[] = { -1, 0, 1, 0 };	// 상 우 하 좌
int dy[] = { 0, 1, 0, -1 };
int minValue = 64;


void getInput() {
	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] <= 5) cam.push_back(make_pair(i, j));
		}
	}
}

void showMap(int map[][MAX_SIZE]) {
	cout << endl << "map is below" << endl;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << map[i][j] << " ";
		}
		cout << endl;
	}
}
void watch(int x, int y, int dir, int tmp_map[][MAX_SIZE]) {
	int nx = 0, ny = 0;
	queue <pair<int, int>> q;
	nx = x + dx[dir];
	ny = y + dy[dir];
	q.push(make_pair(nx, ny));

	while (!q.empty()) {
		nx = q.front().first;
		ny = q.front().second;
		q.pop();
		if (nx < 0 || ny < 0 || nx >= n || ny >= m) return;
		if (tmp_map[nx][ny] == 6) return;
		if (tmp_map[nx][ny] == 0) tmp_map[nx][ny] = 7;
		nx = nx + dx[dir];
		ny = ny + dy[dir];
		q.push(make_pair(nx, ny));
	}
}
void copyMap(int a[][MAX_SIZE], int b[][MAX_SIZE]) {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			b[i][j] = a[i][j];
		}
	}
}
int getScore(int pMap[][MAX_SIZE]) {
	int sum = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (pMap[i][j] == 0) sum++;
		}
	}
	return sum;
}

void dfs(int d, int pMap[][MAX_SIZE]) {	// d = 0부터 시작
	
	if (d == cam.size()) {	// 종료조건에 유의 -> d == n이 아니라 d== n+1에서 종료해야함..
		minValue = min(getScore(pMap), minValue);
		return;
	}
	int tmp_map[MAX_SIZE][MAX_SIZE];
	copyMap(pMap, tmp_map);
	
	int x = cam[d].first;
	int y = cam[d].second;
	int cType = map[x][y];	// 1~5까지
	



	if (cType == 1) {	// 1번 캠은 1개 방향 4개 경우의 수
		for (int i = 0; i < 4; i++) {
			watch(x, y, i, tmp_map);
			dfs(d + 1, tmp_map);
			copyMap(pMap, tmp_map);	// backtracking 을 위한 원복
		}
	}
	if (cType == 2) {
		for (int i = 0; i < 2; i++) {	// 2번캠은 양방향 2개 경우의 수
			watch(x, y, i, tmp_map);
			watch(x, y, i+2, tmp_map);
			dfs(d + 1, tmp_map);
			copyMap(pMap, tmp_map);
		}
	}
	if (cType == 3) {
		for (int i = 0; i < 3; i++) {	//  3번캠 4개 경우의 수
			watch(x, y, i, tmp_map);
			watch(x, y, i + 1, tmp_map);
			dfs(d + 1, tmp_map);
			copyMap(pMap, tmp_map);
		}
	}
	if (cType == 4) {
		for (int i = 0; i < 3; i++) {	// 4번캠은 양방향 4개 경우의 수
			watch(x, y, i, tmp_map);
			watch(x, y, i + 1, tmp_map);
			watch(x, y, (i + 2)%4, tmp_map);
			dfs(d + 1, tmp_map);
			copyMap(pMap, tmp_map);
		}
	}
	if(cType == 5) {
		for (int i = 0; i < 4; i++) {	//  5번캠 1개 경우의 수
			watch(x, y, i, tmp_map);
		}
		dfs(d + 1, tmp_map);
		copyMap(pMap, tmp_map);
	}

}

void setMinimum() {
	int sum = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (map[i][j] == 0) sum++;
		}
	}
	minValue = sum;
}

int main() {
	getInput();
	setMinimum();
	dfs(0, map);
	cout << minValue << endl;

	int wait;
	cin >> wait;
	return 0;
}

lswoo3021 5년 전 1

3번카메라와 4번 카메라의 경우의 수가 누락된 것을 발견해서 수정했더니 통과됐습니다 ㅎㅎ

감사합니당

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

문제

문제

출처

ICPC

반례 및 오류가있을까요!?

lswoo3021 5년 전 1

lswoo3021 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말