[Algorithm/C++17] 백준 17081 RPG Extreme

문제

https://www.acmicpc.net/problem/17081

17081번: RPG Extreme

풀이 방법

문제의 설명이 길지만 설명 그대로 구현하고 시뮬레이션 돌리면 되는 문제다. 옛날 로그 게임 마냥 진행되는데 처리 해줘야 하는 케이스가 많아서 일일이 다 따져보고 구현하고 오류가 날 경우 테스트해봐야 한다.

 

내 경우 어려웠던 케이스는 다음과 같다.

1. 그리드 출력 시 승리 또는 패배 여부에 따른 플레이어의 출력 및 위치
2. 이동 명령 문자열 S가 끝났을 때, 진행된 턴 수 출력
3. 장신구 중복 획득 불가 및 5개 이상 획득 불가
4. 부활 시 부활 장신구 소멸
5. 보스 몬스터와 일반 몬스터의 첫 턴에서 장신구 효과 적용
6. ...

몇 시간에 걸쳐 풀어서 기억이 잘 나지 않는데, 기억 나는 것만 적었는데도 꽤 많다. 풀이 과정 중 예제 입력이 다 맞는데도 37%에서 틀리길래 턴 수 처리를 전부 변경해서 제출했더니 맞았다. 턴 수 처리가 원인인지 루프문 탈출이 원인인지는 잘 모르겠지만 일단 틀린 코드도 아래에 첨부해놓았다.

코드

#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cmath>
using namespace std;
const int CU = 0x1000000;
const int HU = 0x0100000;
const int DX = 0x0010000;
const int EX = 0x0001000;
const int CO = 0x0000100;
const int RE = 0x0000010;
const int HR = 0x0000001;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
class Monster
{
public:
    int r, c;
    string name;
    int dmg, def, maxHp, curHp, exp;

public:
    Monster() {}
    Monster(int y, int x, string _name, int _dmg, int _def, int _maxHp, int _exp) : 
    r(y), c(x), name(_name), dmg(_dmg), def(_def), maxHp(_maxHp), curHp(_maxHp), exp(_exp) {}

    void GetDamaged(int dmg)
    {
        if (dmg <= 0) dmg = 1;
        if (curHp - dmg <= 0) curHp = 0;
        else curHp -= dmg;
    }

    bool Died()
    {
        if (curHp <= 0) return true;
        else return false;
    }
};
struct Chest
{
    int r, c;
    char type;
    string status;
};
class Player
{
public:
    int r, c;
    int level, curHp, maxHp, baseDmg, addDmg, baseDef, addDef, curExp;
    int status; // CU, HU, DX, EX, CO, RE, HR 
    int accessaryCount;

public:
    Player() {}
    Player(int y, int x) : r(y), c(x), level(1), curHp(20), maxHp(20), baseDmg(2), addDmg(0),
        baseDef(2), addDef(0), curExp(0), status(0), accessaryCount(0) {}

    void GetDamaged(int dmg)
    {
        if (dmg <= 0) dmg = 1;
        if (curHp - dmg <= 0) curHp = 0;
        else curHp -= dmg;
    }

    bool Died()
    {
        if (curHp <= 0)
        {
            return true;
        }
        else return false;
    }

    bool CanResurrect()
    {
        return status & RE;
    }

    void Resurrect(int startY, int startX)
    {
        curHp = maxHp;
        r = startY;
        c = startX;
        status &= ~RE;
        accessaryCount--;
    }

    int GetATT(int turn)
    {
        int ret = baseDmg + addDmg;
        if ((status & CO) && (status & DX) && turn == 0)
            return 3 * ret;
        if ((status & CO) && turn == 0)
            return 2 * ret;
        return ret;
    }

    void ObtainItem(const Chest& ch)
    {
        // 무기 획득
        if (ch.type == 'W')
            addDmg = atoi(ch.status.c_str());
        // 방어구 획득
        else if (ch.type == 'A')
            addDef = atoi(ch.status.c_str());
        // 장신구 획득
        else
        {
            if (accessaryCount >= 4) return;
            int before = status;
            if (ch.status == "HR" && !(status & HR)) status |= HR;
            else if (ch.status == "RE" && !(status & RE)) status |= RE;
            else if (ch.status == "CO" && !(status & CO)) status |= CO;
            else if (ch.status == "EX" && !(status & EX)) status |= EX;
            else if (ch.status == "DX" && !(status & DX)) status |= DX;
            else if (ch.status == "HU" && !(status & HU)) status |= HU;
            else if (ch.status == "CU" && !(status & CU)) status |= CU;
            if (before != status) accessaryCount++;
        }
    }

    void ObtainExp(int exp)
    {
        if (status & EX) curExp += floor(exp * 1.2);
        else curExp += exp;

        if (curExp >= 5 * level)
        {
            level++;
            curExp = 0;

            maxHp += 5;
            curHp = maxHp;
            baseDmg += 2;
            baseDef += 2;
        }
    }

    void OnSpikeTrap()
    {
        if (status & DX) GetDamaged(1);
        else GetDamaged(5);
    }

    void AfterCombat()
    {
        if (status & HR)
        {
            if (curHp + 3 < maxHp) curHp += 3;
            else curHp = maxHp;
        }
    }

    void Print()
    {
        printf("LV : %d\n", level);
        printf("HP : %d/%d\n", curHp, maxHp);
        printf("ATT : %d+%d\n", baseDmg, addDmg);
        printf("DEF : %d+%d\n", baseDef, addDef);
        printf("EXP : %d/%d\n", curExp, level * 5);
    }
};
int main()
{
    int N, M;
    scanf("%d %d", &N, &M);
    vector<vector<char>> grid(N + 1, vector<char>(M + 1, '.'));
    vector<Monster> monsters;
    vector<Chest> chests;
    // input
    int monsterCount = 0, chestCount = 0;
    pair<int, int> bossPos;
    pair<int, int> playerPos;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            char c;
            scanf(" %1c", &c);
            grid[i][j] = c;
            if (c == '&')
            {
                monsterCount++;
            }
            else if (c == 'M')
            {
                monsterCount++;
                bossPos = { i,j };
            }
            else if (c == '@')
            {
                playerPos = { i,j };
                grid[i][j] = '.';
            }
            else if (c == 'B')
            {
                chestCount++;
            }
        }
    }
    char str[5001];
    scanf("%s", str);
    for (int i = 0; i < monsterCount; i++)
    {
        int r, c, w, a, h, e;
        char name[11];
        scanf("%d %d %s %d %d %d %d", &r, &c, name, &w, &a, &h, &e);
        Monster m(r, c, name, w, a, h, e);
        monsters.push_back(m);
    }
    for (int i = 0; i < chestCount; i++)
    {
        int r, c;
        char t;
        char s[3];
        scanf("%d %d %c %s", &r, &c, &t, s);
        chests.push_back({ r,c,t,s });
    }

    // simulate
    Player player(playerPos.first, playerPos.second);
    int turn = 0;
    bool win = false, died = false;
    string killerName = "";
    for (turn = 0; str[turn] != '\0'; ++turn)
    {
        // 이동
        if (str[turn] == 'L')
        {
            int ny = player.r + dy[2];
            int nx = player.c + dx[2];
            if (1 <= ny && ny <= N && 1 <= nx && nx <= M && grid[ny][nx] != '#')
            {
                player.r = ny;
                player.c = nx;
            }
        }
        else if (str[turn] == 'R')
        {
            int ny = player.r + dy[3];
            int nx = player.c + dx[3];
            if (1 <= ny && ny <= N && 1 <= nx && nx <= M && grid[ny][nx] != '#')
            {
                player.r = ny;
                player.c = nx;
            }
        }
        else if (str[turn] == 'U')
        {
            int ny = player.r + dy[0];
            int nx = player.c + dx[0];
            if (1 <= ny && ny <= N && 1 <= nx && nx <= M && grid[ny][nx] != '#')
            {
                player.r = ny;
                player.c = nx;
            }
        }
        else
        {
            int ny = player.r + dy[1];
            int nx = player.c + dx[1];
            if (1 <= ny && ny <= N && 1 <= nx && nx <= M && grid[ny][nx] != '#')
            {
                player.r = ny;
                player.c = nx;
            }
        }

        char cur = grid[player.r][player.c];
        // 아이템 상자 획득
        if (cur == 'B')
        {
            // 아이템 획득
            int idx = -1;
            Chest ch;
            for (int j = 0; j < chests.size(); j++)
            {
                if (chests[j].r == player.r && chests[j].c == player.c)
                {
                    ch = chests[j];
                    idx = j;
                    break;
                }
            }
            player.ObtainItem(ch);
            chests.erase(chests.begin() + idx);
            grid[ch.r][ch.c] = '.';
        }
        // 가시함정 밟음
        else if (cur == '^')
        {
            player.OnSpikeTrap();
            if (player.Died())
            {
                if (player.CanResurrect())
                {
                    player.Resurrect(playerPos.first, playerPos.second);
                }
                else
                {
                    died = true;
                    killerName = "SPIKE TRAP";
                    turn++;
                    break;
                }
            }
        }
        // 몬스터
        else if (cur == '&')
        {
            int idx = -1;
            Monster m;
            for (int j = 0; j < monsters.size(); j++)
            {
                if (monsters[j].r == player.r && monsters[j].c == player.c)
                {
                    m = monsters[j];
                    idx = j;
                    break;
                }
            }
            // 전투
            for (int j = 0; ; j++)
            {
                m.GetDamaged(player.GetATT(j) - m.def);
                if (m.Died())
                {
                    player.ObtainExp(m.exp);
                    monsters.erase(monsters.begin() + idx);
                    grid[m.r][m.c] = '.';
                    break;
                }

                player.GetDamaged(m.dmg - (player.baseDef + player.addDef));
                if (player.Died())
                {
                    if (player.CanResurrect())
                    {
                        player.Resurrect(playerPos.first, playerPos.second);
                        m.curHp = m.maxHp;
                        break;
                    }
                    else
                    {
                        died = true;
                        killerName = m.name;
                        break;
                    }
                }
            }
            // 전투 끝
            if (!died) player.AfterCombat();
            else
            {
                turn++;
                break;
            }
        }
        // 보스 몬스터
        else if (cur == 'M')
        {
            int idx = -1;
            Monster m;
            for (int j = 0; j < monsters.size(); j++)
            {
                if (monsters[j].r == player.r && monsters[j].c == player.c)
                {
                    m = monsters[j];
                    idx = j;
                    break;
                }
            }
            // 전투
            for (int j = 0; ; j++)
            {
                m.GetDamaged(player.GetATT(j) - m.def);
                if (m.Died())
                {
                    player.ObtainExp(m.exp);
                    monsters.erase(monsters.begin() + idx);
                    grid[m.r][m.c] = '.';
                    break;
                }
                player.GetDamaged(m.dmg - (player.baseDef + player.addDef));
                // Hunter(HU) : 보스 몬스터와 전투에 돌입하는 순간 체력을 최대치까지 회복하고, 보스 몬스터의 첫 공격에 0의 데미지를 입는다.
                // 그냥 첫 공격 받은 후에 최대체력으로 회복시킴
                if ((player.status & HU) && j == 0)
                {
                    player.curHp = player.maxHp;
                }

                if (player.Died())
                {
                    if (player.CanResurrect())
                    {
                        player.Resurrect(playerPos.first, playerPos.second);
                        m.curHp = m.maxHp;
                        break;
                    }
                    else
                    {
                        died = true;
                        killerName = m.name;
                        break;
                    }
                }
            }
            // 보스 전투 끝
            if (!died && m.curHp == 0)
            {
                player.AfterCombat();
                win = true;
                turn++;
                break;
            }
            else if (died)
            {
                turn++;
                break;
            }
        }
    }
    // Print the grid
    if (!died) grid[player.r][player.c] = '@';
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            printf("%c", grid[i][j]);
        }
        printf("\n");
    }
    // Print the passed turns
    printf("Passed Turns : %d\n", turn);
    // Print the player status
    player.Print();
    // Print the result
    if (win)
    {
        printf("YOU WIN!");
    }
    else if (died)
    {
        printf("YOU HAVE BEEN KILLED BY %s..", killerName.c_str());
    }
    else
    {
        printf("Press any key to continue.");
    }
    return 0;
}

37%에서 틀렸던 코드

#include <cstdio>
#include <vector>
#include <string>
#include <cstdlib>
#include <cmath>
using namespace std;
const int CU = 0x1000000;
const int HU = 0x0100000;
const int DX = 0x0010000;
const int EX = 0x0001000;
const int CO = 0x0000100;
const int RE = 0x0000010;
const int HR = 0x0000001;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
class Monster
{
public:
    int r, c;
    string name;
    int dmg, def, maxHp, curHp, exp;

public:
    Monster() {}
    Monster(int y, int x, string _name, int _dmg, int _def, int _maxHp, int _exp) : 
    r(y), c(x), name(_name), dmg(_dmg), def(_def), maxHp(_maxHp), curHp(_maxHp), exp(_exp) {}

    void GetDamaged(int dmg)
    {
        if (dmg <= 0) dmg = 1;
        if (curHp - dmg <= 0) curHp = 0;
        else curHp -= dmg;
    }

    bool Died()
    {
        if (curHp <= 0) return true;
        else return false;
    }
};
struct Chest
{
    int r, c;
    char type;
    string status;
};
class Player
{
public:
    int r, c;
    int level, curHp, maxHp, baseDmg, addDmg, baseDef, addDef, curExp;
    int status; // CU, HU, DX, EX, CO, RE, HR 
    int accessaryCount;

public:
    Player() {}
    Player(int y, int x) : r(y), c(x), level(1), curHp(20), maxHp(20), baseDmg(2), addDmg(0),
        baseDef(2), addDef(0), curExp(0), status(0), accessaryCount(0) {}

    void GetDamaged(int dmg)
    {
        if (dmg <= 0) dmg = 1;
        if (curHp - dmg <= 0) curHp = 0;
        else curHp -= dmg;
    }

    bool Died()
    {
        if (curHp <= 0)
        {
            return true;
        }
        else return false;
    }

    bool CanResurrect()
    {
        return status & RE;
    }

    void Resurrect(int startY, int startX)
    {
        curHp = maxHp;
        r = startY;
        c = startX;
        status &= ~RE;
        accessaryCount--;
    }

    int GetATT(int turn)
    {
        int ret = baseDmg + addDmg;
        if ((status & CO) && (status & DX) && turn == 0)
            return 3 * ret;
        if ((status & CO) && turn == 0)
            return 2 * ret;
        return ret;
    }

    void ObtainItem(const Chest& ch)
    {
        // 무기 획득
        if (ch.type == 'W')
            addDmg = atoi(ch.status.c_str());
        // 방어구 획득
        else if (ch.type == 'A')
            addDef = atoi(ch.status.c_str());
        // 장신구 획득
        else
        {
            if (accessaryCount >= 4) return;
            int before = status;
            if (ch.status == "HR" && !(status & HR)) status |= HR;
            else if (ch.status == "RE" && !(status & RE)) status |= RE;
            else if (ch.status == "CO" && !(status & CO)) status |= CO;
            else if (ch.status == "EX" && !(status & EX)) status |= EX;
            else if (ch.status == "DX" && !(status & DX)) status |= DX;
            else if (ch.status == "HU" && !(status & HU)) status |= HU;
            else if (ch.status == "CU" && !(status & CU)) status |= CU;
            if (before != status) accessaryCount++;
        }
    }

    void ObtainExp(int exp)
    {
        if (status & EX) curExp += floor(exp * 1.2);
        else curExp += exp;

        if (curExp >= 5 * level)
        {
            level++;
            curExp = 0;

            maxHp += 5;
            curHp = maxHp;
            baseDmg += 2;
            baseDef += 2;
        }
    }

    void OnSpikeTrap()
    {
        if (status & DX) GetDamaged(1);
        else GetDamaged(5);
    }

    void AfterCombat()
    {
        if (status & HR)
        {
            if (curHp + 3 < maxHp) curHp += 3;
            else curHp = maxHp;
        }
    }

    void Print()
    {
        printf("LV : %d\n", level);
        printf("HP : %d/%d\n", curHp, maxHp);
        printf("ATT : %d+%d\n", baseDmg, addDmg);
        printf("DEF : %d+%d\n", baseDef, addDef);
        printf("EXP : %d/%d\n", curExp, level * 5);
    }
};
int main()
{
    int N, M;
    scanf("%d %d", &N, &M);
    vector<vector<char>> grid(N + 1, vector<char>(M + 1, '.'));
    vector<Monster> monsters;
    vector<Chest> chests;
    // input
    int monsterCount = 0, chestCount = 0;
    pair<int, int> bossPos;
    pair<int, int> playerPos;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            char c;
            scanf(" %1c", &c);
            grid[i][j] = c;
            if (c == '&')
            {
                monsterCount++;
            }
            else if (c == 'M')
            {
                monsterCount++;
                bossPos = { i,j };
            }
            else if (c == '@')
            {
                playerPos = { i,j };
                grid[i][j] = '.';
            }
            else if (c == 'B')
            {
                chestCount++;
            }
        }
    }
    char str[5001];
    scanf("%s", str);
    for (int i = 0; i < monsterCount; i++)
    {
        int r, c, w, a, h, e;
        char name[11];
        scanf("%d %d %s %d %d %d %d", &r, &c, name, &w, &a, &h, &e);
        Monster m(r, c, name, w, a, h, e);
        monsters.push_back(m);
    }
    for (int i = 0; i < chestCount; i++)
    {
        int r, c;
        char t;
        char s[3];
        scanf("%d %d %c %s", &r, &c, &t, s);
        chests.push_back({ r,c,t,s });
    }

    // simulate
    Player player(playerPos.first, playerPos.second);
    int turn = 0;
    bool win = false, died = false;
    string killerName = "";
    for (int i = 0; str[i] != '\0'; i++)
    {
        turn = i;
        if (win || died) break;
        if (str[i] == 'L')
        {
            int ny = player.r + dy[2];
            int nx = player.c + dx[2];
            if (1 <= ny && ny <= N && 1 <= nx && nx <= M && grid[ny][nx] != '#')
            {
                player.r = ny;
                player.c = nx;
            }
        }
        else if (str[i] == 'R')
        {
            int ny = player.r + dy[3];
            int nx = player.c + dx[3];
            if (1 <= ny && ny <= N && 1 <= nx && nx <= M && grid[ny][nx] != '#')
            {
                player.r = ny;
                player.c = nx;
            }
        }
        else if (str[i] == 'U')
        {
            int ny = player.r + dy[0];
            int nx = player.c + dx[0];
            if (1 <= ny && ny <= N && 1 <= nx && nx <= M && grid[ny][nx] != '#')
            {
                player.r = ny;
                player.c = nx;
            }
        }
        else
        {
            int ny = player.r + dy[1];
            int nx = player.c + dx[1];
            if (1 <= ny && ny <= N && 1 <= nx && nx <= M && grid[ny][nx] != '#')
            {
                player.r = ny;
                player.c = nx;
            }
        }

        char cur = grid[player.r][player.c];
        // 아이템 상자 획득
        if (cur == 'B')
        {
            // 아이템 획득
            int idx = -1;
            Chest ch;
            for (int j = 0; j < chests.size(); j++)
            {
                if (chests[j].r == player.r && chests[j].c == player.c)
                {
                    ch = chests[j];
                    idx = j;
                    break;
                }
            }
            player.ObtainItem(ch);
            chests.erase(chests.begin() + idx);
            grid[ch.r][ch.c] = '.';
        }
        // 가시함정 밟음
        else if (cur == '^')
        {
            player.OnSpikeTrap();
            if (player.Died())
            {
                if (player.CanResurrect())
                {
                    player.Resurrect(playerPos.first, playerPos.second);
                }
                else
                {
                    died = true;
                    killerName = "SPIKE TRAP";
                }
            }
        }
        // 몬스터
        else if (cur == '&')
        {
            int idx = -1;
            Monster m;
            for (int j = 0; j < monsters.size(); j++)
            {
                if (monsters[j].r == player.r && monsters[j].c == player.c)
                {
                    m = monsters[j];
                    idx = j;
                    break;
                }
            }
            // 전투
            for (int j = 0; ; j++)
            {
                m.GetDamaged(player.GetATT(j) - m.def);
                if (m.Died())
                {
                    player.ObtainExp(m.exp);
                    monsters.erase(monsters.begin() + idx);
                    grid[m.r][m.c] = '.';
                    break;
                }

                player.GetDamaged(m.dmg - (player.baseDef + player.addDef));
                if (player.Died())
                {
                    if (player.CanResurrect())
                    {
                        player.Resurrect(playerPos.first, playerPos.second);
                        m.curHp = m.maxHp;
                        break;
                    }
                    else
                    {
                        died = true;
                        killerName = m.name;
                        break;
                    }
                }
            }
            // 전투 끝
            if (!died) player.AfterCombat();
        }
        // 보스 몬스터
        else if (cur == 'M')
        {
            int idx = -1;
            Monster m;
            for (int j = 0; j < monsters.size(); j++)
            {
                if (monsters[j].r == player.r && monsters[j].c == player.c)
                {
                    m = monsters[j];
                    idx = j;
                    break;
                }
            }
            // 전투
            for (int j = 0; ; j++)
            {
                m.GetDamaged(player.GetATT(j) - m.def);
                if (m.Died())
                {
                    player.ObtainExp(m.exp);
                    monsters.erase(monsters.begin() + idx);
                    grid[m.r][m.c] = '.';
                    break;
                }
                player.GetDamaged(m.dmg - (player.baseDef + player.addDef));
                if ((player.status & HU) && j == 0)
                {
                    player.curHp = player.maxHp;
                }

                if (player.Died())
                {
                    if (player.CanResurrect())
                    {
                        player.Resurrect(playerPos.first, playerPos.second);
                        m.curHp = m.maxHp;
                        break;
                    }
                    else
                    {
                        died = true;
                        killerName = m.name;
                        break;
                    }
                }
            }
            // 전투 끝
            if (!died && m.curHp == 0)
            {
                player.AfterCombat();
                win = true;
            }
        }
    }
    // Print the grid
    if (!died) grid[player.r][player.c] = '@';
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            printf("%c", grid[i][j]);
        }
        printf("\n");
    }
    // Print the passed turns
    if (!win && !died) turn++;
    printf("Passed Turns : %d\n", turn);
    // Print the player status
    player.Print();
    // Print the result
    if (win)
    {
        printf("YOU WIN!");
    }
    else if (!win && died)
    {
        printf("YOU HAVE BEEN KILLED BY %s..", killerName.c_str());
    }
    else
    {
        printf("Press any key to continue.");
    }
    return 0;
}

고찰

구현 문제집을 보다가 RPG가 있길래 풀어본 문제... 읽고 언뜻 보기에 쉬울 것 같아 도전해봤는데 역시 내 티어보다 높은 문제라 그런지 꽤 시간이 많이 걸렸다. 신경 써줘야하는 케이스가 많아서 까다로웠다.

 

처음에 아이템 상자와 몬스터 정보를 저장할 자료구조로 좌표를 키 값으로 unordered_map을 사용할까했다. 이렇게 하면 좌표로 O(1)에 해당 몬스터의 데이터를 얻을 수 있기 때문이다. 그러나 몬스터도 이동하는 줄 알고(좌표가 변경되는 줄 알고) 그냥 vector에 담아서 순회해 O(n)에 찾는 식으로 했다. 그러나 구현하다보니 몬스터가 이동할 수 없는 문제였는데, 중간에 수정하기가 좀 번거로워서 그냥 진행했다...