글 읽기 - 질문게시판의 테스트케이스를 통과하고도 98%에서 틀렸다고 나옵니다

james66won 4년 전 1

저랑 비슷한 질문이 있어서 그 게시물에 댓글로 달린 반례를 모두 테스트 해보았는데도 98%에서 틀리네요..

제가 미처 잡지 못한 반례를 찾아주시면 정말 감사하겠습니다.

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

// a배열은 지도, tot은 전체 빈칸(0)의 개수, vnum은 총 바이러스의 수
// co배열은 조합을 만들기 위해 사용하는 배열, ans는 최종 정답인 최솟값
// first는 처음 BFS시행인지 아닌지 확인하는 flag변수, 처음 시행을 하면 1로 바뀜
int N, M, a[50][50], tot=0, vnum, co[10]={0,}, ans, first=0;
vector<pair<int, int>> virus; // 2를 입력받으면 virus vector에 삽입

int bfs() {
	queue<pair<int, int>> q;
    // cnt는 빈칸을 바이러스로 채울 때마다 1 증가시킴
	int r, c, v[50][50]={{0,},0}, dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}}, cnt=0;
	for (int i=0; i<vnum; i++) {
		if (co[i]==1) {
			v[virus[i].first][virus[i].second]=1;
			q.push(make_pair(virus[i].first, virus[i].second));
            // 활성 바이러스로 채택된 바이러스를 방문하고 큐에 넣음
            // v배열은 방문 안한 원소를 구분하기 위해 편의상 1부터 시작
            // 다만 0초부터 시작하므로 마지막에 1을 빼주고 return함
		}
	}
	while(!q.empty()) {
		r=q.front().first;
		c=q.front().second;
		q.pop();
		for (int i=0; i<4; i++) { // 네 방향 탐색
			int newr=r+dir[i][0];
			int newc=c+dir[i][1];
			if (newr<0||newr>=N||newc<0||newc>=N) continue; // 경계를 벗어난 경우 거넌뜀
			if (a[newr][newc]==1) continue; // 벽인 경우 건너뜀
			if (v[newr][newc]>0) continue; // 이미 방문한 경우 건너뜀
			v[newr][newc]=v[r][c]+1; // 새로운 칸을 전염시킨 시간은 1초 후
			if (a[newr][newc]==0) cnt++; // 빈칸을 전염시킬 때 cnt값을 1 증가시킴
			if (cnt==tot) return v[newr][newc]-1; // 모든 칸을 전염시켰다면 그때까지 걸린 시간을 return
			q.push(make_pair(newr, newc));
		}
	}
	if (cnt==tot) return v[r][c]-1; // 빈칸이 없어 0초가 걸린 경우
	else return -1; // 모든 빈칸을 채우지 못한 경우 -1을 return
}

void com(int idx, int r) {
	if (r==0) { // 더이상 뽑을 것이 없을 때, 즉 M개를 모두 다 뽑았을 때
		int min=bfs(); // min은 한번의 bfs 시행 후 모든 칸을 다 칠하기까지 걸린 시간
		if (first==0) { // 처음 시행인 경우 비교 대상이 없으므로 ans를 min으로 씀
			ans=min;
			first=1;
		}
		else {
			if (ans==-1) ans=min; // 기존의 ans가 -1인 경우 ans를 min으로 씀
			else if (min!=-1&&min<ans) ans=min; // min이 -1이 아니면서 ans보다 작은 경우 ans가 바뀜
		}
	}
	else if (idx==vnum) return; // 뽑을 것이 남아있지만 index를 벗어난 경우
	else {
		co[idx]=1;
		com(idx+1, r-1); // 현재 idx번째 바이러스를 선택하면 남은 것중 r-1개 선택
		co[idx]=0;
		com(idx+1, r); // 현재 idx번째 바이러스를 선택 안하면 남은 것중 r개 선택
	}
}

int main(void) {
	cin >> N >> M;
	for (int i=0; i<N; i++) {
		for (int j=0; j<N; j++) {
			cin >> a[i][j];
			if (a[i][j]==0) tot++; // tot은 전체 빈칸의 개수를 셈
			else if (a[i][j]==2) virus.push_back(make_pair(i, j)); // virus를 만난 경우 virus vector에 삽입
		}
	}
	vnum=virus.size();
	com(0, M); // M개의 조합을 만드는 과정(0번째 virus부터 M개 선택)
	cout << ans << endl;
	return 0;
}

james66won 4년 전 1

해결했습니다. tot이 0인 경우를 처음부터 거르면 해결되네요

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

문제

문제

출처

ICPC

질문게시판의 테스트케이스를 통과하고도 98%에서 틀렸다고 나옵니다

james66won 4년 전 1

james66won 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말