글 읽기 - 연구소 3 테스트케이스는 맞았는데 어떤부분에서 틀린걸까요?

kiwonlee95 4년 전 0

90% 까지 맞다가 90%에서 틀립니다 ㅠㅠ

문제에 있는 테스트 케이스는 맞았는데 어디서 잘못된걸까요?

저는 DFS로 M개의 연구소를 고르고 다시 BFS로 탐색하였습니다

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#pragma warning(disable : 4996)
using namespace std;

struct POS
{
	int x, y, count = 0;
};

bool visited[51][51];
int map[51][51];
int N, M, ans = 987654321;

vector<POS> candi_virus;
vector<POS> virus;

const int dx[4] = { -1, 1, 0, 0 };
const int dy[4] = { 0, 0, -1, 1 };

void BFS(int temp[][51])
{
	queue<POS> q;
	
	for (int i = 0; i < virus.size(); i++)
	{
		q.push(virus[i]);
	}

	int candi = 0;
	while (!q.empty())
	{
		POS cur = q.front();
		q.pop();
		
		if(cur.count > candi)
			candi = cur.count;

		visited[cur.x][cur.y] = true;
		temp[cur.x][cur.y] = 3;

		for (int dir = 0; dir < 4; dir++)
		{
			int next_x = cur.x + dx[dir], next_y = cur.y + dy[dir];

			if (next_x < 0 || next_y < 0 || next_x >= N || next_y >= N)
				continue;

			if (visited[next_x][next_y] == false && temp[next_x][next_y] == 0 && cur.count < ans)
			{
				visited[next_x][next_y] = true;
				POS next;
				next.x = next_x, next.y = next_y, next.count = cur.count + 1;
				q.push(next);
			}
		}
	}
	bool isOK = true;
	for (int i = 0; i < N && isOK; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (temp[i][j] == 0)
			{
				isOK = false;
				break;
			}
		}
	}

	if (isOK)
	{
		if (candi < ans)
			ans = candi;
	}
}
void DFS(int start)
{
	if (virus.size() == M)
	{
		int temp[51][51];
		memcpy(temp, map, sizeof(temp));
		memset(visited, false, sizeof(visited));

		// 바이러스 확산
		BFS(temp);
		
		return;
	}

	for (int i = start + 1; i < candi_virus.size(); i++)
	{
		if (map[candi_virus[i].x][candi_virus[i].y] == 2)
		{
			map[candi_virus[i].x][candi_virus[i].y] = 3;
			virus.push_back(candi_virus[i]);
			DFS(i);
			map[candi_virus[i].x][candi_virus[i].y] = 2;
			virus.pop_back();
		}
	}
}

int main()
{
	scanf("%d %d", &N, &M);

	
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			scanf("%d", &map[i][j]);

			if (map[i][j] == 2)
			{
				POS candi;
				candi.x = i, candi.y = j;
				candi_virus.push_back(candi);
			}
		}
	}

	for (int i = 0; M + i <= candi_virus.size(); i++)
	{
		virus.push_back(candi_virus[i]);
		map[candi_virus[i].x][candi_virus[i].y] = 3;

		DFS(i);

		virus.pop_back();
		map[candi_virus[i].x][candi_virus[i].y] = 2;
	}

	if (ans == 987654321)
		cout << "-1" << endl;
	else
		cout << ans << endl;

    return 0;
}

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

문제

문제

출처

ICPC

연구소 3 테스트케이스는 맞았는데 어떤부분에서 틀린걸까요?

kiwonlee95 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말