코드트리 - 왕실의 기사 대결 [C++]

이 문제는 시뮬레이션 문제이다.

 

이 문제에서 핵심은 연쇄적으로 발생하는 기사들의 움직임을 구현하는 것이다. 나는 이걸 구현하기 위해 재귀를 사용했다.

어떤 기사가 어떤 방향으로 움직여야할 때, 방패까지 포함한 자신의 경계를 구하고, 그 경계에서 다음 위치를 확인한 뒤 만약 다른 기사가 있어면 그 기사에 대해 재귀적으로 호출하는 방식으로 구현했다.

 

실제로 움직임을 구현할 때 주의해야할 점이 있는데, 우선 이미 움직인 기사를 또 움직이면 안된다. 내 코드의 경우 move 함수 안에서 candidate를 뽑아 진행하는데, 중복이 가능하여 처음에 오답이 나왔었다.

또한 움직인 기사들 말고도 안 움직인 기사들도 다음 벡터에 남아야 한다. 너무 당연한 로직인데 항상 실수하는 부분인 것 같다.

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

#define KNIGHT_MAX 30

#define EMPTY 0
#define BAD 1
#define WALL 2

#define UP 0
#define RIGHT 1
#define DOWN 2
#define LEFT 3

struct Knight {
    int y;
    int x;
    int h;
    int w;
    int k;  
};

vector<Knight> knights;
vector<vector<int>> board;
vector<vector<int>> knightBoard;
int score[KNIGHT_MAX + 1];
int L, N, Q;

vector<pair<int, int>> getBorder(int y, int x, int h, int w, int direction) {
    vector<pair<int, int>> yx;
    
    switch (direction) {
        case UP:
            for (int nx = x; nx <= x + w - 1; nx++) {
                yx.push_back({y, nx});
            }
            break;
        case DOWN:
            for (int nx = x; nx <= x + w - 1; nx++) {
                yx.push_back({y + h - 1, nx});
            }
            break;
        case RIGHT:
            for (int ny = y; ny <= y + h - 1; ny++) {
                yx.push_back({ny, x + w - 1});
            }
            break;
        case LEFT:
            for (int ny = y; ny <= y + h - 1; ny++) {
                yx.push_back({ny, x});
            }
            break;
    }

    return yx;
}

int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};

bool inRange(int y, int x) {
    return (1 <= y && y <= L && 1 <= x && x <= L);
}

bool canMove(int knightNumber, int direction) {
    if (knights[knightNumber].y == -1) {
        return false;
    }
    
    Knight& present = knights[knightNumber];
    int y = present.y;
    int x = present.x;
    int h = present.h;
    int w = present.w;

    vector<pair<int, int>> yx = getBorder(y, x, h, w, direction);
    
    for (pair<int, int>& next : yx) {
        int ny = next.first + dy[direction];
        int nx = next.second + dx[direction];

        if (!inRange(ny, nx)) {
            return false;
        }

        if (board[ny][nx] == WALL) {
            return false;
        }

        if (knightBoard[ny][nx] == 0) {
            continue;
        }

        if (knightBoard[ny][nx] > 0) {
            if (canMove(knightBoard[ny][nx], direction)) {
                continue;
            } else {
                return false;
            }
        }
    }

    return true;
}

vector<int> findCandidate(int knightNumber, int direction) {
    Knight& present = knights[knightNumber];
    int y = present.y;
    int x = present.x;
    int h = present.h;
    int w = present.w;

    vector<pair<int, int>> yx = getBorder(y, x, h, w, direction);
    vector<int> result;
    result.push_back(knightNumber);

    for (pair<int, int>& next : yx) {
        int ny = next.first + dy[direction];
        int nx = next.second + dx[direction];

        if (!inRange(ny, nx)) {
            continue;
        }

        if (knightBoard[ny][nx] > 0) {
            vector<int> rest = findCandidate(knightBoard[ny][nx], direction);

            for (int r : rest) {
                result.push_back(r);
            }
        }
    }

    return result;
}

void draw(vector<vector<int>>& nextBoard, int num, int y, int x, int h, int w) {
    for (int ny = y; ny <= y + h - 1; ny++) {
        for (int nx = x; nx <= x + w - 1; nx++) {
            nextBoard[ny][nx] = num;
        }
    }
} 

void move(int knightNumber, int direction) {
    vector<vector<int>> nextBoard(L + 1, vector<int>(L + 1, 0));
    vector<int> candidate = findCandidate(knightNumber, direction);

    // present move
    Knight& presentKnight = knights[knightNumber];
    presentKnight.y += dy[direction];
    presentKnight.x += dx[direction];
    draw(nextBoard, knightNumber, presentKnight.y, presentKnight.x, presentKnight.h, presentKnight.w);    

    vector<bool> visited(N + 1, false);
    visited[knightNumber] = true;

    for (int i = 1; i < candidate.size(); i++) {
        int num = candidate[i];

        if (visited[num]) {
            continue;
        }

        visited[num] = true;

        Knight& knight = knights[num];

        
        knight.y += dy[direction];
        knight.x += dx[direction];

        int bad = 0;
        for (int ny = knight.y; ny <= knight.y + knight.h - 1; ny++) {
            for (int nx = knight.x; nx <= knight.x + knight.w - 1; nx++) {
                if (board[ny][nx] == BAD) {
                    bad++;
                }
            }
        }

        if (knight.k <= bad) {
            knight.y = -1;
            score[num] = 0;
        } else {
            knight.k -= bad;
            score[num] += bad;
            draw(nextBoard, num, knight.y, knight.x, knight.h, knight.w);
        }
    }

    for (int i = 1; i <= N; i++) {
        if (!visited[i]) {
            Knight& present = knights[i];

            if (present.y == -1) {
                continue;
            }

            draw(nextBoard, i, present.y, present.x, present.h, present.w);
        }
    }

    knightBoard = nextBoard;
}

void print() {
    for (int y = 1; y <= L; y++) {
        for (int x = 1; x <= L; x++) {
            cout << knightBoard[y][x] << " ";
        }
        cout << '\n';
    }
    cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> L >> N >> Q;
    
    board = vector<vector<int>>(L + 1, vector<int>(L + 1));
    knightBoard = vector<vector<int>>(L + 1, vector<int>(L + 1, 0));
    knights = vector<Knight>(N + 1);

    for (int y = 1; y <= L; y++) {
        for (int x = 1; x <= L; x++) {
            cin >> board[y][x];
        }
    }

    for (int i = 1; i <= N; i++) {
        int r, c, h, w, k;

        cin >> r >> c >> h >> w >> k;
        knights[i] = {r, c, h, w, k};
        for (int y = r; y <= r + h - 1; y++) {
            for (int x = c; x <= c + w - 1; x++) {
                knightBoard[y][x] = i;
            } 
        }
    }

    //cout << "initial state" << '\n';
    //print();
    //cout << '\n';

    for (int q = 0; q < Q; q++) {
        int i, d;
        cin >> i >> d;
        
        if (canMove(i, d)) {
            move(i, d);
        }

        //print();
    }
    
    int answer = 0;
    for (int i = 1; i <= N; i++) {
        answer += score[i];
    }

    cout << answer << '\n';

    return 0;
}