BOJ

BOJ::17081 RPG Extreme

BOJ Platinum 1

BOJ::17081 RPG Extreme

Link : BOJ::17081
Level : Platinum 1
tag : implementation

시사점

정말 좋은, 재밌는 구현 문제입니다.
할 수 있는 모든 실수들을 한 것 같지만, 너무 겁내지 않고 모듈화해가며 구현하였습니다.

이해(x)

시키는대로 구현합니다.
설명이 너무 길어질 수 있으므로, 결론만 말하자면,
게임이 종료되는 경우는 다음의 4가지가 있습니다.
- 주인공이 가시에 마지막 데미지를 입어 죽은 경우
- 주인공이 몬스터와 싸우다가 죽은 경우
- 모든 라운드를 진행한 경우
- 주인공이 보스 몬스터를 잡아서 이긴 경우

설계, 손 코딩(x)

손으로 중심이 되는 코드를 구현합니다.
문제에서 요청하는 바가 많습니다.
- 최대한 함수를 잘게 잘게 쪼개고,
- counter part인 함수 하나의 비중을 낮춰가는 방향으로 설계하였습니다.
- 또한, 값이 섞이지 않도록, 주인공, 몬스터, 아이템 각각 구조체를 사용했습니다.

시간 복잡도

공간 복잡도

손 코딩 후 문제 리뷰(x)

빼먹고 손 코딩 한 것이 있는지 확인합니다.

구현(x)

함수 List

void PRINT(); : 게임 종료시, 맵을 출력합니다.
void PRINT3(int idx, int who, int exitreason); : 게임 종료시, 주인공의 상태 및 사유를 출력합니다.

void input(); : 모든 입력을 받습니다.
 - void input_mp();  : 맵의 상태를 입력받습니다.
 - void input_move();  : 시뮬레이션 돌릴 이동방향을 입력받습니다.
 - void input_mons();  : 몬스터의 신상을 입력받습니다.
 - void input_items(); : 아이템 관련 사항을 입력받습니다.
void init(); : 주인공의 상태를 초기화합니다.
bool over(int x, int y); 
void getItem(int x, int y); : 이동 중 아이템이 있는 칸으로 간 경우, 처리해주는 함수
void getMonster(int x, int y); : 이동 중 몬스터를 만난 경우, 처리해주는 함수
void process(); 전반적으로 모든 시뮬레이션 과정을 담고 있습니다.

업데이트 되는 변수

대부분의 디버깅 문제는 업데이트 되는 변수에서 발생합니다.

실제 구현

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
const int MAXNM = 100, SCRACH = 5;
const char DIR[]={'U','R','D','L'};
const int dx[]={-1, 0, 1, 0}, dy[]={0, 1, 0, -1};
enum ac {HR = 0, RE, CO, EX, DX, HU, CU};
std::string seq[]={"HR", "RE", "CO", "EX", "DX", "HU", "CU"};
struct mon{int atk; int shield; int mxHp; int curHp; int giveExp;std::string ss;};
struct itms{char T; int addup;};
struct hero{int x; int y; int atk; int sword; int shield; int cover; int mxHp; int curHp; int curExp; int mxExp; int Lvl; int cntAccs; bool accs[7];};
using namespace std;

int n, m, sx, sy;
int cntmons, cntitems;
char mp[MAXNM][MAXNM];
int mp_item[MAXNM][MAXNM];
int mp_mons[MAXNM][MAXNM];
vector<int> moves;

hero me;
vector<mon> monsters;
vector<itms> items;
void PRINT();
void PRINT3(int idx, int who, int exitreason);
void input(); void input_mp(); void input_move(); void input_mons(); void input_items();
void init();
bool over(int x, int y);
void getItem(int x, int y);
void getMonster(int x, int y);
// mp[x][y] = {'.', '#', 'B', '^', '&', 'M'}
// 종료 조건 = { me.curHP <= 0(monster와 싸워서), me.curHP <= 0(트랩 밟아서), M잡은 경우, moves다 돈 경우, }
void process(){
    int idx = 0, who  = 0, exitreason = 3;
    input();
    init();
    rep(i, 0, moves.size()){
        idx = i;
        int nx = me.x + dx[moves[i]], ny = me.y + dy[moves[i]];
        if(over(nx, ny) || mp[nx][ny] == '#'){
			nx = me.x, ny = me.y;
            if(mp[me.x][me.y] == '^') me.curHp -= SCRACH/(me.accs[DX]?5:1);
            goto here;
        }
        else if(mp[nx][ny] == '^') me.curHp -= SCRACH/(me.accs[DX]?5:1);
        else if(mp[nx][ny] == '.') ;
        else if(mp[nx][ny] == 'B'){
            getItem(nx, ny);
            mp[nx][ny] = '.';
        }else if(mp[nx][ny] == '&' || mp[nx][ny] == 'M'){
            getMonster(nx, ny);
            if(me.curHp > 0){
                if(mp[nx][ny] == 'M'){
                    mp[nx][ny] = '.';
                    me.x = nx, me.y = ny;
                    exitreason = 2;
                    break;
                }
                mp[nx][ny] = '.';
            }
            else{
                who = mp_mons[nx][ny];
            }
        }else { /* Do nothing */ }
        me.x = nx, me.y = ny;
    here:;
        if(me.curHp <= 0 && me.accs[RE]) me.x = sx, me.y = sy, me.curHp = me.mxHp, me.accs[RE] = false;
        // 끝에서 체력확인
        if(me.curHp <= 0){
            if(mp[nx][ny] == '^' || over(nx, ny))exitreason = 1;
            else exitreason = 0;
            break;
        }
    }
    PRINT();
    PRINT3(idx, who, exitreason);
}
int main(){
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    process();
    return 0;
}
void getMonster(int x, int y){
    // before fight
    struct mon curMon = monsters[mp_mons[x][y]];
    if(mp[x][y] == 'M' && me.accs[HU]) me.curHp = me.mxHp;
	int rnd = 0;
	while(true){
		int me_atk = me.atk + me.sword;
        if(rnd == 0 && me.accs[CO]) me_atk *= (2+ me.accs[DX]);
        int me_shield = me.shield + me.cover;
        // me -> monster
        curMon.curHp -= max(1, me_atk - curMon.shield);
        if(curMon.curHp <= 0) break;

        // me <- monster
        if(rnd == 0 && mp[x][y] == 'M' && me.accs[HU]) ;
        else me.curHp -= max(1, curMon.atk - me_shield);
        if(me.curHp <= 0) break;
		rnd++;
	}
    // after fight
    if(me.curHp > 0){
        if(me.accs[HR]) me.curHp = min(me.curHp +3, me.mxHp);
        me.curExp += (double)curMon.giveExp * ((double)1 +(double)(me.accs[EX]?0.2:0) );
        if(me.curExp >= me.mxExp){
            ++me.Lvl, me.curExp = 0, me.mxExp = me.Lvl * 5;
            me.mxHp += 5, me.atk += 2, me.shield += 2;
            me.curHp = me.mxHp;
        }
    }else{

    }
}
void getItem(int x, int y){
    struct itms curItm = items[mp_item[x][y]];
    if(curItm.T == 'W') me.sword = curItm.addup;
    else if(curItm.T == 'A') me.cover = curItm.addup;
    else{
        if(me.cntAccs < 4 && !me.accs[curItm.addup]){
            me.accs[curItm.addup] = true;
            me.cntAccs++;
        }
    }
}
bool over(int x, int y){ return (x<0 || y<0 || x>=n || y>=m);}
void init(){
    // hero
    me.x = sx, me.y = sy;
    me.atk = 2, me.shield = 2, me.curHp = 20, me.mxHp = 20, me.Lvl = 1;
    me.curExp = 0, me.mxExp = me.Lvl * 5;
}
void input_mp(){
    cin >> n >> m;
    rep(i, 0, n){
        rep(j, 0, m){
            cin >> mp[i][j];
            if(mp[i][j] == '@'){
                mp[i][j] = '.';
                sx = i, sy = j;
            }else if(mp[i][j] == '&' || mp[i][j] == 'M'){
                mp_mons[i][j] = cntmons++;
            }else if(mp[i][j] == 'B'){
                mp_item[i][j] = cntitems++;
            }
        }
    }
}
void input_move(){
    string s; cin >> s;
    rep(i, 0, s.size()){
        rep(k, 0, 4) if(DIR[k] == s[i]){
            moves.push_back(k);
            break;
        }
    }
}
void input_mons(){
    monsters = vector<mon> (cntmons);
    rep(i, 0, cntmons){
        int r, c; string name; int atk, shield, mxHp, giveExp;
        cin >> r >> c >> name >> atk >> shield >> mxHp >> giveExp;
        monsters[mp_mons[r-1][c-1]] = {atk, shield, mxHp, mxHp, giveExp, name};
    }
}
void input_items(){
    items = vector<itms> (cntitems);
    rep(i, 0, cntitems){
        int r, c; char T; int si= -1; string ss;
        cin >> r >> c >> T;
        if(T == 'O'){
            cin >> ss;
            rep(k, 0, 7) if(strcmp(seq[k].c_str(), ss.c_str()) == 0){
                si = k;
                break;
            }
        }
        else cin >> si;
        items[mp_item[r-1][c-1]] = {T, si};
    }
}
void input(){
    input_mp();
    input_move();
    input_mons();
    input_items();
}
void PRINT(){
    rep(i, 0, n){
        rep(j, 0, m){
            if(i == me.x && j == me.y && me.curHp > 0) cout << '@';
            else cout << mp[i][j];
        }cout << endl;
    }
}
// 종료 조건 = { me.curHP <= 0(monster와 싸워서), me.curHP <= 0(트랩 밟아서), M잡은 경우, moves다 돈 경우, }
void PRINT3(int idx, int who, int reason){
    cout << "Passed Turns : " << idx+1 << endl;
    cout << "LV : " << me.Lvl << endl;
    cout << "HP : " << max(0, me.curHp) << "/" << me.mxHp << endl;
    cout << "ATT : " << me.atk<< "+"<<me.sword << endl;
    cout << "DEF : " << me.shield <<"+"<<me.cover << endl;
    cout << "EXP : " << me.curExp <<"/" << me.mxExp << endl;
    if(reason == 0){
        cout << "YOU HAVE BEEN KILLED BY " << monsters[who].ss <<".." << endl;
    }else if(reason == 1){
        cout << "YOU HAVE BEEN KILLED BY SPIKE TRAP.." << endl;
    }else if(reason == 2){
        cout << "YOU WIN!" << endl;
    }else{
        cout << "Press any key to continue." << endl;
    }
}

구현 후 코드리뷰 + 예제 돌려보기(x)

바로 예제를 넣어서 테스트 해보기 전에, 코드를 한 번 리뷰하고, 예제의 입력이 이런식으로 왔을때 전체 코드가 어떤 식으로 순차적으로 진행되는지 답은 잘 도출될 것 같은지 확인합니다.

디버깅(x)

많은 실수들을 하였고, 기억나는 것만 되짚어 보겠습니다.
- 몬스터, 아이템에 대한 정보는 총 2번 입력됩니다.
  - 즉, 주어진 맵에 표시된 것과 추후에 리스트를 입력받는 것입니다.
  - 맵에 표시된 순으로 각 아이템의 위치를 index화 하였습니다.
  - 그리고, 리스트를 입력받았을때 matching시켜주는 작업을 합니다.
  - 이때, 각 맵에 써진 인덱스를 사용해야 하지만, 리스트에 들어오는 순서인 인덱스를 사용했습니다.
- 다시 말해, 몬스터는 mp_mons[][], 아이템은 mp_item[][]에 각 넘버링을 저장해둡니다.
- 마지막으로 가장 오랜 시간 디버깅 했던 것은 nx, ny에 대한 처리입니다.
- process함수에서 시뮬레이션을 돌릴때,
  - nx, ny가 맵을 벗어나려 하거나, 벽으로 가려하였다면 nx, ny를 다시 rollback해주어야 뒷처리가 매끄럽습니다.
  - 하지만, 빼먹고 구현하였었습니다.
- 그 외에도 등호를 안붙인 것과, 등등이 있지만 추후에 다시 돌아와서 2nd try해보겠습니다.

BOJ::17081 RPG Extreme

BOJ Platinum 1

BOJ::17081 RPG Extreme

시사점

이해(x)

설계, 손 코딩(x)

시간 복잡도

공간 복잡도

손 코딩 후 문제 리뷰(x)

구현(x)

함수 List

업데이트 되는 변수

실제 구현

구현 후 코드리뷰 + 예제 돌려보기(x)

디버깅(x)

좋은 코드

최적화