글 읽기 - test case는 다 맞는데 어디가 틀린 걸까요?

ds04030 4년 전 0

dfs로 '2' 중에 M개를 선택합니다.
재귀함수로 바이러스를 퍼트립니다.

- 바이러스를 퍼트리는 함수는 solve이며 매개변수로 time과 num을 받습니다.

- time은 현재 몇 초가 지났는지를 나타내며 num은 남은 빈 공간이 몇개 인지를 나타냅니다! ( 당연히 활성화된 바이러스, 비활성화된 바이러스, 벽은 제외합니다.)

- 빈 공간에 바이러스를 퍼트리면 남은 빈공간의 수를 하나씩 줄여나갑니다..

- 그렇게 계속 바이러스를 퍼트리다가 남은 빈공간의 수가(num) 0이 되면 result값을 갱신합니다.

위와 같은 알고리즘으로 구현했는데.. 왜 계속 틀렸다고 나오는 걸까요?

혹시 오류를 발견하셨다면 알려주시면 감사하겠습니다. ^^

/*
	연구소 3
*/

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

char map[50][50], temp[50][50];
int N, M;
int result = 987654321;
void  dfs(int cnt, int pick);
pair<int, int> vir[10];
vector<pair<int, int> > liveVir;
bool visited[10] = { false, };
int numOfVirus = 0;
const int dx[] = { 0,0,1,-1 };
const int dy[] = { 1,-1,0,0 };
void solve(int time, int num);
void makeTemp();
int tempCount = 0;

int main()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> map[i][j];
			if (map[i][j] == '2') {
				vir[numOfVirus] = { i,j };
				numOfVirus++;
			}
			else if (map[i][j] == '0') {
				tempCount++;
			}
		}
	}

	dfs(0, 0);
	if (tempCount == 0) {
		cout << "0" << "\n";
	}
	else if (result == 987654321) {
		cout << "-1" << "\n";
	}
	else {
		cout << result << "\n";
	}
	return 0;
}

// '2'가 위치한 곳중 활성화 시킬것 정하기
void dfs(int cnt, int pick) {
	if (cnt == M) {
		makeTemp();
		solve(0, tempCount);
		return;
	}

	for (int i = pick; i < numOfVirus; i++) {
		if (!visited[i]) {
			visited[i] = true;
			dfs(cnt + 1,i + 1);
			visited[i] = false;
		}
	}
}

// 바이러스 퍼트리기. time:몇 초가 지났는지 num:빈 공간의 수
void solve(int time, int num) {
	if (num == 0) {
		if (time < result)result = time;
		return;
	}

	int Count = num;
    bool change = false;
    
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (temp[i][j] - '0' == time) {
				for (int d = 0; d < 4; d++) {
					if (i + dx[d] >= 0 && i + dx[d] < N && j + dy[d] >= 0 && j + dy[d] < N) {
						// 빈공간이면 Count수 감소
                        if (temp[i + dx[d]][j + dy[d]] == '!') {
							Count--;
							temp[i + dx[d]][j + dy[d]] = static_cast<char>(static_cast<int>(temp[i][j]) + 1);
							
						}
                        // 비활성화 바이러스가 있다면 Count 수는 그대로
						else if (temp[i + dx[d]][j + dy[d]] == '*') {
							temp[i + dx[d]][j + dy[d]] = static_cast<char>(static_cast<int>(temp[i][j]) + 1);
						    change = true;
                        }
					}
				}
			}
		}
	}

    // 빈 공간의 수가 줄어들거나 비활성화 바이러스가 활성화가 되면
	if (Count < num || change == true) {
		solve(time + 1, Count);
	}
    
    // 만약 바이러스가 이제 더이상 퍼질 수 없다면 볼 필요도 없으므로 return.
	else {
		return;
	}
}

void makeTemp() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == '0') temp[i][j] = '!';
			else if (map[i][j] == '1') temp[i][j] = '-';
		}
	}

	for (int i = 0; i < numOfVirus; i++) {
		int x = vir[i].first;
		int y = vir[i].second;
		if (visited[i]) {
			temp[x][y] = '0';
			liveVir.push_back({ x,y });
		}
		else {
			temp[x][y] = '*';
		}
	}
}

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

문제

문제

출처

ICPC

test case는 다 맞는데 어디가 틀린 걸까요?

ds04030 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말