글 읽기 - 98에서 틀렸다고 나옵니다....도와주시면 감사드리겠습니다ㅜㅜ

shvk54 4년 전 0

98퍼센트에서 틀렸다고 나오네요ㅠㅠ 저는 각 궁수를 3명 배치하는 모든 경우의 수를 구현하고 그 궁수 한명마다 bfs를 통해 거리를 계산하도록 구현했습니다...ㅜㅜ 어느 부분을 제가 고려안한걸까요ㅜㅜ

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

int N, M, D;
vector<vector<int>>adj,dp,Copy;
vector<int>V;
vector<bool>selected;
vector<vector<bool>>shot;
int result1 = 0;
int result2 = 0;

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

void bfs(int x, int y) {
	queue<pair<int, int>>q;
	vector<pair<int, int>>T;//사정거리 내의 적을 담을 배열->가장 가까운 왼쪽에 존재하는 적을 가려내기 위해 여기에 담음
	int Min = 100;
	int Min_index = 0;
	dp[y][x] = 0;
	q.push(make_pair(y, x));
	while (!q.empty()) {
		pair<int, int>here = q.front();
		if (dp[here.first][here.second] > D)
		{
			if (T.empty())
				return;
			for (int i = 0; i < T.size(); ++i)			
				Min = min(Min, dp[T[i].first][T[i].second]);//가장 가까운 적의 위치까지의 거리를 min에 저장
			
			for (int i = 0; i < T.size(); ++i)
			{
				if (dp[T[i].first][T[i].second] == Min)
				{
					if (T[i].second < T[Min_index].second)//가장 가까운 적이 여러명일 때 가장 왼쪽의 적을 확인하기 위한 구현
						Min_index = i;
				}
			}
			
			if (shot[T[Min_index].first][T[Min_index].second] == false)
			{
				result1++;//중복되지 않게 적을 죽일 경우에만 result를 증가시켜준다
				shot[T[Min_index].first][T[Min_index].second] = true;
			}
			return;
		}
		q.pop();
		for (int i = 0; i < 4; ++i)
		{
			int nx = here.second + dx[i];
			int ny = here.first + dy[i];
			if (nx < 1 || ny<1 || nx>M || ny>N + 1)
				continue;
			if (dp[ny][nx] == -1) {
				dp[ny][nx] = dp[here.first][here.second] + 1;
				q.push(make_pair(ny, nx));
				if (Copy[ny][nx] == 1 && dp[ny][nx] <= D)//적이 있고, 적까지의 거리가 D보다 작거나 같을 경우에 T에 담아준다.
					T.push_back(make_pair(ny, nx));
			}
		}
	}
}

void solve(int cnt, int start)//궁수 3명을 배치하는 모든 경우의 수
{
	if (cnt == 3)//3명의 궁수를 모두 배치 할 때
	{
		Copy = adj;
		for (auto x : V)
			Copy[N + 1][x] = -1;
		
		result1 = 0;
		for (int t = 1; t <= N; ++t) {
			shot = vector<vector<bool>>(N + 2, vector<bool>(M + 1, false));//궁수가 중복된 적을 죽일 수 있기 때문에 확인하기 위한 vector
			for (auto x : V)
			{
				dp = vector<vector<int>>(N + 2, vector<int>(M + 1, -1));//각각 궁수로 부터 bfs를 시행하여 거리를 담고 있는 vector
				bfs(x, N + 1);
			}
			for (int i = 1; i <= N; ++i)
			{
				for (int j = 1; j <= M; ++j)
					if (shot[i][j] == true)
						Copy[i][j] = 0;//적을 죽이면 배열에 반영을 시켜줌
			}
			for (int i = N; i >= 2; --i)//적이 한칸씩 내려옴을 구현
				for (int j = 1; j <= M; ++j)
					Copy[i][j] = Copy[i - 1][j];
			for (int j = 1; j <= M; ++j)
				Copy[1][j] = 0;
		}
		result2 = max(result2, result1);
		return;
	}
	else
	{
		for (int i = start; i <= M; ++i)
		{
			if (!selected[i])
			{
				selected[i] = true;
				V.push_back(i);
				solve(cnt + 1, i + 1);
				selected[i] = false;
				V.pop_back();
			}
		}
	}

}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> N >> M >> D;
	adj = vector<vector<int>>(N + 2, vector<int>(M + 1, 0));
	selected = vector<bool>(M + 1, false);
	for (int i = 1; i <= N; ++i)
		for (int j = 1; j <= M; ++j)
			cin >> adj[i][j];

	solve(0, 1);
	cout << result2;

	return 0;
}

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

문제

문제

출처

ICPC

98에서 틀렸다고 나옵니다....도와주시면 감사드리겠습니다ㅜㅜ

shvk54 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말