보스몬스터 전리품
문제 해석
최대 몇명의 플레이어가 전리품을 얻을 수 있는지 알아내는 문제입니다.
지도, 플레이어들의 정보, 보스몬스터의 체력에 대한 정보가 주어집니다.
모든 플레이어는 보스의 위치를 최단경로로 이동합니다. 이때 드는 시간은 각 1초입니다.
이후에 보스의 위치에 도착하면 공격을 시작하는데 이 또한 1초가 소모됩니다.
플레이어는 상,하,좌,우로 이동할 수 있습니다.
설계(10)
유저들을 이동시키고 보스의 체력이 0이하가 될때까지 공격을 하는 방식으로 구성이 가능합니다. 유저를 최단거리로 이동시키기 위해서 bfs알고리즘을 사용하였습니다.
각 유저가 최대 26명 있으므로 유저들의 이동상태를 표현할 3차원 배열이 필요합니다. (visited[1000][1000][26])
보스 몬스터의 위치에 도착한 유저를 is_attack변수에 체크를 하여서 공격가능한 사람을 추립니다.
매번 1번 이동한 후, 공격 한번해주는 방식으로 구현하면 O(MxNx26)=O(2.6x10^7)로 시간안에 통과가 가능합니다.
구현을 다 하고 다른분들의 풀이를 보았을 때 약간 충격을 받았습니다. 일단 제가 구현한 실행시간보다 훨씬 빨랐습니다.
해당 방식을 보니, 발상의 전환으로 보스가 각 유저들에게 움직이는 방식을 이용한 것입니다.
그렇게 될 경우, O(MxN)=O(10^6)으로 훨씬 빠른 시간에 통과할 수 있습니다.
구현(20)
코드1(유저이동방식)
#include <iostream>
#include <queue>
using namespace std;
#define MAXN 1000
int M, N, K,HP;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
bool visited[MAXN][MAXN][26];
struct node {
int idx, x, y;
};
queue<node> q;
char arr[MAXN][MAXN];
int attack[26];
bool can_attack[26];
int bfs() {
while (HP > 0) {
int q_size = q.size();
while (q_size--) {
int idx = q.front().idx;
int x = q.front().x;
int y = q.front().y;
q.pop();
if (can_attack[idx]) continue;
if (arr[x][y] == 'B') {
can_attack[idx] = true;
}
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
if (visited[nx][ny][idx] || arr[nx][ny] == 'X') continue;
visited[nx][ny][idx] = true;
q.push({idx,nx,ny });
}
}
for (int i = 0; i < 26; i++) {
if (can_attack[i]) HP -= attack[i];
}
}
int ans = 0;
for (int i = 0; i < 26; i++) {
ans += can_attack[i];
}
return ans;
}
int main() {
cin >> M >> N >> K;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
cin >> arr[i][j];
if (arr[i][j] >= 'a' && arr[i][j] <= 'z') {
q.push({arr[i][j]-'a', i,j });
visited[i][j][arr[i][j] - 'a'] = true;
}
}
}
for (int i = 0; i < K; i++) {
char c;
int num;
cin >> c >> num;
attack[c - 'a'] = num;
}
cin >> HP;
cout << bfs();
return 0;
}
코드2(보스이동방식)
#include <iostream>
#include <queue>
using namespace std;
#define MAXN 1000
int M, N, K, HP;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
bool visited[MAXN][MAXN];
queue<pair<int,int> > q;
char arr[MAXN][MAXN];
int attack[26];
bool can_attack[26];
int bfs() {
while (HP > 0) {
int q_size = q.size();
while (q_size--) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (arr[x][y] >= 'a' && arr[x][y] <= 'z') {
can_attack[arr[x][y] - 'a'] = true;
}
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
if (visited[nx][ny] || arr[nx][ny] == 'X') continue;
visited[nx][ny] = true;
q.push({ nx,ny });
}
}
for (int i = 0; i < 26; i++) {
if (can_attack[i]) HP -= attack[i];
}
}
int ans = 0;
for (int i = 0; i < 26; i++) {
ans += can_attack[i];
}
return ans;
}
int main() {
cin >> M >> N >> K;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {
cin >> arr[i][j];
if (arr[i][j] == 'B'){
q.push({ i,j });
visited[i][j] = true;
}
}
}
for (int i = 0; i < K; i++) {
char c;
int num;
cin >> c >> num;
attack[c - 'a'] = num;
}
cin >> HP;
cout << bfs();
return 0;
}
디버깅
제출결과
140 ms(각 유저이동방식) 52 ms(보스 이동방식)
마무리
단순 구현만 하면 되는 문제였습니다. 하지만 발상을 전환시키면 더욱 최적화가 가능하였습니다. 이런 아이디어를 생각하기 위해서 고정적인 시각으로 바라보는 습관을 없애야할 것 같습니다.