코드트리 - 왕실의 기사 대결

왕실의 기사 대결

코드트리 Gold 3 Simulation BFS
코드트리 - 왕실의 기사 대결

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 풀이

마법의 숲 탐색에서 했던 방식처럼 테두리에 패딩을 둬 바운더리를 체크하지 않아도 되도록 했다.

기사가 명령을 받아 움직이기 시작할 때, 필드에 있는 기사끼리의 상호작용이 핵심인 문제였다.
기사가 밀쳐졌을 경우, 이동해야 하는 위치에 벽이 있다면 전체 상호작용이 없던 셈 쳐지고, 해당 턴이 사라지는 것과 같은 효과가 있었다.

이를 해결하기 위해 여러 방법을 시도해 봤지만, 쉽지 않았고 답을 확인했었는데,
그냥 필드를 복사해서 두번 체크해보면 되는 것 이었다.

주어지는 필드의 크기가 그렇게 크지 않고, 명령의 수가 최대 100개만 주어지기 때문에, 한 명령을 두번씩 시행한다고 생각해도 시간적으로 빡빡하지 않았었다.

이런식으로 생각해본적이 없어서 좀 오래 해맸던 것 같다.

코드

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <unordered_set>

using namespace std;

struct nightInfo {
    int x, y, health, maxHP, width, height;
    bool isLive;

    nightInfo () : x(0), y(0), maxHP(0), health(0), width(0), height(0), isLive(true) {}
};

vector<vector<int>> fld;
unordered_map<int, nightInfo> nights;
int mv[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

bool tryIsAvail (int num, int& dir) {
    vector<vector<int>> fld2 = fld;
    queue<int> q;
    unordered_set<int> ck;

    q.push(num);
    ck.insert(num);

    while (!q.empty()) {
        num = q.front(); q.pop();
        int x = nights[num].x;
        int y = nights[num].y;
        for (int i=x; i<x+nights[num].height; i++) {
            for (int j=y; j<y+nights[num].width; j++) {

                int dx = i + mv[dir][0];
                int dy = j + mv[dir][1];
                fld2[i][j] -= num;
                int tmp = fld2[dx][dy]%2 ? fld2[dx][dy]-1 : fld2[dx][dy];

                if (fld2[dx][dy] == 2) return false;
                if (fld2[dx][dy] > 3 && ck.count(tmp) == 0) {
                    ck.insert(tmp);
                    q.push(tmp);
                }

                fld2[dx][dy] += num;
            }
        }
    }
    return true;
}

void simulation(int num, int& dir) {
    if (!tryIsAvail(num, dir)) return ;

    queue<int> q;
    unordered_set<int> ck;

    q.push(num);
    ck.insert(num);

    while (!q.empty()) {
        int nightNum = q.front(); q.pop();
        int x = nights[nightNum].x;
        int y = nights[nightNum].y;
        int cnt = 0;
        nights[nightNum].x += mv[dir][0];
        nights[nightNum].y += mv[dir][1];

        for (int i=x; i<x+nights[nightNum].height; i++) {
            for (int j=y; j<y+nights[nightNum].width; j++) {
                int dx = i + mv[dir][0];
                int dy = j + mv[dir][1];
                fld[i][j] -= nightNum;
                int tmp = fld[dx][dy]%2 ? fld[dx][dy]-1 : fld[dx][dy];
                if (fld[dx][dy] > 3 && ck.count(tmp) == 0) {
                    ck.insert(tmp);
                    q.push(tmp);
                }
                fld[dx][dy] += nightNum;
                if (fld[dx][dy]%2) cnt++;
            }
        }
        if (nightNum == num) continue;
        nights[nightNum].health -= cnt;
        if (nights[nightNum].health <= 0) {
            nights[nightNum].isLive = false;
            for (int i=nights[nightNum].x; i<nights[nightNum].x+nights[nightNum].height; i++) {
                for (int j=nights[nightNum].y; j<nights[nightNum].y+nights[nightNum].width; j++) fld[i][j] -= nightNum;
            }
        }
    }

    return ;
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int L, N, Q, res=0;

    cin >> L >> N >> Q;
    fld.resize(L+2, vector<int>(L+2, 2));

    for (int i=1; i<=L; i++) {
        for (int j=1; j<=L; j++) {
            cin >> fld[i][j];
        }
    }

    for (int i=2; i<=N+1; i++) {
        nightInfo tmp;
        cin >> tmp.x >> tmp.y >> tmp.height >> tmp.width >> tmp.health;
        tmp.maxHP = tmp.health;
        for (int h=tmp.x; h<tmp.x+tmp.height; h++) {
            for (int w=tmp.y; w<tmp.y+tmp.width; w++) {
                fld[h][w] += i*2;
            }
        }
        nights[i*2] = tmp;
    }

    for (int q=0; q<Q; q++) {
        int i, d;
        cin >> i >> d;
        if (!nights[i*2+2].isLive) continue;

        simulation(i*2+2, d);
    }

    for (auto night : nights) {
        if (!night.second.isLive) continue;
        res += night.second.maxHP - night.second.health;
    }

    cout << res << "\n";

    return 0;
}

후기

점점 디버깅이 안될 때 어떻게 대처해야할 지 방법들을 하나하나 모으고 있는 것 같다.

주어진 필드에 패딩을 주거나, 같은 작업을 두번 반복 한다거나 하는 것 같은..