글 읽기 - [15683 감시] 제출하자마자 1초컷 당해서 질문 올립니다.

mo0nlight0 3년 전 0

안녕하세요.

게시판에 있는 예제들은 어지간하면 다 넣어보았고, 정답이 잘 출력되는 것을 확인했습니다.

그런데, 제출하기만 하면 1초컷으로 틀렸습니다를 받게 되어 질문 올립니다.

혹시 제가 찾지 못한 코드의 오류나 다른 반례가 있을까요?

#include <bits/stdc++.h>

#define X first
#define Y second

using namespace std;

vector<pair<int, int>> v;
int minimum = 65;
int room[9][9];
bool board[9][9][9];
int n, m;

void color_board(int idx) { // 그 전 노드에서 보드의 값들을 가져옴
	if (idx == 0) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (room[j][i] == 6) // 벽일경우
					board[idx][j][i] = 1;
				else
					board[idx][j][i] = 0;
			}
		}
		return;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			board[idx][j][i] = board[idx-1][j][i]; // 그 전 보드의 값 복사
	}
}

void func(int idx) {
	if (idx == v.size()){ // 마지막 카메라까지 넣은 후, 최솟값 계산
		int cnt = 0;
		int tmp;
		for (int i = 0; i < n; i++) {
			for (int j = 0 ; j < m ; j++){
				if (idx == 0) {
					if (board[idx][j][i] == 1)
						cnt++;
				}
				else {
					if (board[idx - 1][j][i] == 1)
						cnt++;
				}
			}
		}
		tmp = m * n - cnt;
		if (minimum > tmp) 
			minimum = tmp;
		
		return;
	}

	if (room[v[idx].X][v[idx].Y] == 1) { // 1번 유형 카메라
		int dx[4] = { 1,0,-1,0 };
		int dy[4] = { 0,1,0,-1 };
		for (int dir = 0; dir < 4; dir++) {
			color_board(idx);
			board[idx][v[idx].X][v[idx].Y] = 1;
			int nx = v[idx].X + dx[dir];
			int ny = v[idx].Y + dy[dir];
			while (nx >= 0 && nx < m && ny >= 0 && ny < n) {
				if (room[nx][ny] == 6) 
					break;
				board[idx][nx][ny] = 1;
				nx += dx[dir];
				ny += dy[dir];
			}
			func(++idx);
			idx--;
		}
	}
	if (room[v[idx].X][v[idx].Y] == 2) { // 2번 유형 카메라
		int top_x = v[idx].X;
		int bot_x = v[idx].X;
		int top_y = v[idx].Y;
		int bot_y = v[idx].Y;
		color_board(idx);
		board[idx][v[idx].X][v[idx].Y] = 1;
		while (top_x < m){
			if (room[top_x][v[idx].Y] == 6) 
				break;
			
			board[idx][top_x++][v[idx].Y] = 1;
		}
		while (bot_x >= 0) {
			if (room[bot_x][v[idx].Y] == 6)
				break;
			board[idx][bot_x--][v[idx].Y] = 1;
		}
		
		func(++idx);
		idx--;
		color_board(idx);
		board[idx][v[idx].X][v[idx].Y] = 1;
		while (top_y < n) {
			if (room[v[idx].X][top_y] == 6)
				break;

			board[idx][v[idx].X][top_y++] = 1;
		}
		while (bot_y >= 0) {
			if (room[v[idx].X][bot_y] == 6)
				break;
			board[idx][v[idx].X][bot_y--] = 1;
		}
		func(++idx); 
		idx--;
	}
	if (room[v[idx].X][v[idx].Y] == 3) { // 3번 유형 카메라
		int dx[4] = { 1,1,-1,-1 };
		int dy[4] = { 1,-1,-1,1 };
		for (int dir = 0; dir < 4; dir++) {
			color_board(idx);
			board[idx][v[idx].X][v[idx].Y] = 1;
			int nx = v[idx].X + dx[dir];
			int ny = v[idx].Y + dy[dir];
			while (nx < m && nx >= 0) {
				if (room[nx][v[idx].Y] == 6)
					break;
				board[idx][nx][v[idx].Y] = 1;
				nx += dx[dir];
			}
			while (ny < n && ny >= 0) {
				if (room[v[idx].X][ny] == 6)
					break;
				board[idx][v[idx].X][ny] = 1;
				ny += dy[dir];
			}
			func(++idx);
			idx--;
		}
	}
	if (room[v[idx].X][v[idx].Y] == 4) { // 4번 유형 카메라
		for (int i = 0; i < 4; i++) {
			int top_x = v[idx].X + 1;
			int bot_x = v[idx].X - 1;
			int top_y = v[idx].Y + 1;
			int bot_y = v[idx].Y - 1;
			color_board(idx);
			board[idx][v[idx].X][v[idx].Y] = 1;
			while (top_x < m && i != 0) {
				if (room[top_x][v[idx].Y] == 6)
					break;
				board[idx][top_x++][v[idx].Y] = 1;
			}
			while (top_y < n && i != 1) {
				if (room[v[idx].X][top_y] == 6)
					break;
				board[idx][v[idx].X][top_y++] = 1;
			}
			while (bot_x >= 0 && i != 2) {
				if (room[bot_x][v[idx].Y] == 6)
					break;
				board[idx][bot_x--][v[idx].Y] = 1;
			}
			while (bot_y >= 0 && i != 3) {
				if (room[v[idx].X][bot_y] == 6)
					break;
				board[idx][v[idx].X][bot_y--] = 1;
			}
			func(++idx);
			idx--;
		}
	}
	if (room[v[idx].X][v[idx].Y] == 5) { // 5번 유형 카메라
		int top_x = v[idx].X + 1;
		int bot_x = v[idx].X - 1;
		int top_y = v[idx].Y + 1;
		int bot_y = v[idx].Y - 1;
		color_board(idx);
		board[idx][v[idx].X][v[idx].Y] = 1;
		while (top_x < m) {
			if (room[top_x][v[idx].Y] == 6)
				break;
			board[idx][top_x++][v[idx].Y] = 1;
		}
		while (top_y < n) {
			if (room[top_x][v[idx].Y] == 6)
				break;
			board[idx][v[idx].X][top_y++] = 1;
		}
		while (bot_x >= 0) {
			if (room[bot_x][v[idx].Y] == 6)
				break;
			board[idx][bot_x--][v[idx].Y] = 1;
		}
		while (bot_y >= 0) {
			if (room[v[idx].X][bot_y] == 6)
				break;
			board[idx][v[idx].X][bot_y--] = 1;
		}
		func(++idx);
		idx--;
	}
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int tmp;
			cin >> tmp;
			if (tmp != 0 && tmp != 6)
				v.push_back({ j,i }); // 카메라들의 위치를 저장
			if (tmp == 6)
				board[0][j][i] = 1; // 벽은 감시할 필요가 없음
			room[j][i] = tmp; // 칸마다의 값 저장
		}
	}

	func(0);

	cout << minimum;

	return 0;
}

koreandns 3년 전 5

반례 입니다.

input

5 5
5 1 6 1 4
6 0 1 6 3
2 5 0 0 0
0 6 0 0 0
6 0 6 6 6

output

answer

koreandns 3년 전 2

찾기 쉬운 반례입니다.

input

3 1
5
6
0

output

answer

mo0nlight0 3년 전 0

감사합니다 덕분에 해결했습니다!

이 코드 부분에서 room[top_x][v[idx].Y] 부분을 짤 때 top_x 부분을 복붙하고 수정을 안 해버렸네요...

while (top_y < n) {
			if (room[top_x][v[idx].Y] == 6)
				break;
			board[idx][v[idx].X][top_y++] = 1;
		}

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

문제

문제

출처

ICPC

[15683 감시] 제출하자마자 1초컷 당해서 질문 올립니다.

mo0nlight0 3년 전 0

koreandns 3년 전 5

koreandns 3년 전 2

mo0nlight0 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말