글 읽기 - 19537 전투 시뮬레이션 질문드립니다ㅠ

kysu5095 3년 전 0

19537 전투 시뮬레이션 질문드립니다.

기본적으로 문제를 푸는 방식은 우선순위 큐를 사용하여 다이스트라 알고리즘 형태로 풀었습니다.

일반적인 다이스트라랑 다른 부분이라면 다음칸으로 이동하는 루틴을 수행하기 이전에

사방을 확인하면서 주변에 적이 있는지 확인하는 것이고, 없다면 다음칸으로 갈 수 있는지 판별 후 큐에 넣어주었습니다.

또한 제가 이해한 명령을 수행하지 못하는 경우는

1. 도착 지점에 유닛이 있는경우

2. 도착 지점이 갈 수 없는 지형인 경우(-1)

3. 이동중 주변에 적이 있어 교전이 발생한 경우

4. 이동중 갈 수 없는 지형을 만나거나 스태미너를 모두 소모했을 경우

입니다.

제가 문제를 잘 못 이해한건지 바로 틀렸습니다가 떠버리네요ㅠ

혹시 코드나 이해한 부분에서 지적할 부분이 있다면 지적해주시면 감사하겠습니다.

// 전투 시뮬레이션

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>

using namespace std;

int n, h, w, m, k;
int arr[501][501] = { {0,}, }; /* 험준도 */
int map[501][501] = { {0,}, }; /* 맵에 존재하는 유닛 번호표시(벡터의 인덱스) */
int visited[501][501] = { {0, }, };
int slope[10];
int dy[4] = { 0 ,0 ,1 ,-1 };
int dx[4] = { 1, -1, 0, 0 };

class Unit {
public:
	int m, t, y, x;
};
vector<Unit> v;

bool move(int& u, int& _y, int& _x) {
	if (map[_y][_x]) return false; /* 도착지점에 유닛이 있음 */
	if (slope[arr[_y][_x]] == -1) return false; /* 갈 수 없는 지형 */
	int y = v[u].y, x = v[u].x;
	int s = v[u].m, t = v[u].t;
	priority_queue<pair<int, pair<int, int>>> pq;
	pq.push(make_pair(s, make_pair(y, x)));
	visited[y][x] = s;
	int ny, nx, ns;
	bool flag;
	while (!pq.empty()) {
		s = pq.top().first;
		y = pq.top().second.first;
		x = pq.top().second.second;
		pq.pop();
		if (s < visited[y][x]) continue;
		flag = true;
		/* 현 위치에서 주변에 적이 있다면 정지 */
		for (int i = 0; i < 4; i++) {
			ny = y + dy[i];
			nx = x + dx[i];
			if (ny < 0 || ny == h || nx < 0 || nx == w) continue;
			if (map[ny][nx] && v[map[ny][nx]].t != t) { /* 유닛이 존재하고 그 유닛이 적일 경우 == 교전 */
				flag = false;
				break;
			}
		}
		if (!flag) continue;

		/* 다음칸으로 이동가능한지 판별 */
		for (int i = 0; i < 4; i++) {
			ny = y + dy[i];
			nx = x + dx[i];
			if (ny < 0 || ny == h || nx < 0 || nx == w) continue; /* 범위체크 */
			ns = s - slope[arr[ny][nx]]; /* 소모한 스태미너 */ 
			if (slope[arr[ny][nx]] == -1 || ns < 0) continue; /* 갈 수 없는 지형이거나 스태미너 초과 */
			if (ny == _y && nx == _x) return true; /* 목표도착 */
			if (ns <= visited[ny][nx]) continue;
			pq.push(make_pair(ns, make_pair(ny, nx)));
			visited[ny][nx] = ns;
		}
	}
	return false;
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	int a, b, c, d;
	cin >> n >> h >> w;
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			cin >> arr[i][j];
	for (int i = 1; i <= n; i++)
		cin >> slope[i];

	v.push_back({ 0, 0, 0, 0 }); /* 1번 index부터 시작하기위해 넣어줌 */
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> a >> b >> c >> d;
		v.push_back({ a, b, c, d });
		map[c][d] = i; /* 맵에 유닛 표시 */
	}
	cin >> k;
	for (int i = 0; i < k; i++) {
		cin >> a >> b >> c;
		memset(visited, 0, sizeof(visited));
		if (move(a, b, c)) { /* 명령 수행 */
			map[b][c] = a;
			map[v[a].y][v[a].x] = 0;
			v[a].y = b;
			v[a].x = c;
		}
	}
	for (int i = 1; i <= m; i++) 
		cout << v[i].y << " " << v[i].x << '\n';
	return 0;
}

ckdgus2482 3년 전 0

디스크립션을 보면 다음과 같은 문구가 있습니다.

"하지만, 선택된 유닛이 이미 교전 상태였다면 약진하여 교전에서 벗어날 수 있다."

적대 세력 유닛이 서로 인접한 상황에서 약진 명령을 수행할 수 있는 경우도 있는데 올려주신 코드는 탐색을 진행하지 않습니다.

kysu5095 3년 전 0

@ckdgus2482 앗 의견 감사드립니다ㅠ

저는 저 문구를 그냥 언제든지 이동할 수 있다고 생각하고 대수롭게 생각하였는데 다시보니 처음부터 교전중인 상황에서 진행이 불가능 하군요

다시 풀어보겠습니다. 감사합니다!

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

문제

문제

출처

ICPC

19537 전투 시뮬레이션 질문드립니다ㅠ

kysu5095 3년 전 0

ckdgus2482 3년 전 0

kysu5095 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말