문제 링크

삼성 코딩테스트 기출 문제: 왕실의 기사 대결 - 코드트리

주요 IT 기업의 코딩테스트 기출 문제를 연습하며 실전 감각을 키우세요. 취업 합격률을 높이는 필수 연습 과정입니다.

코드트리

문제 설명

LL 크기의 체스판이 있음. 각 칸은 빈칸, 함정, 벽으로 구성되어 있고, 체스판 밖도 벽으로 간주함. 왕실의 기사의 초기 위치는 (r,c)이며, 해당 위치를 좌측 상단으로 하며 hw의 직사각형 형태를 띄고 있음. 그리고 기사의 체력은 k임.

1. 기사 이동왕에게 명령을 받은 기사는 상하좌우로 한 칸 이동함. 이동하려는 위치에 기사가 있다면 해당 기사는 연쇄적으로 밀리게 됨. 만약 끝에 벽이 있다면, 모든 기사는 이동할 수 없게 됨. 사라진 기사에게 명령을 내리면 아무 반응이 없음.
2. 대결 데미지명령을 받은 기사가 다른 기사를 밀치게 되면, 밀려난 기사들은 피해를 입게 됨. 각 기사들이 이동한 곳에서 h*w 직사각형 내에 놓여 있는 함정의 수 만큼 피해를 입게 됨. 현재 체력 이상의 데미지를 받을 경우 체스판에서 사라지게 됨. 단, 명령을 받은 기사는 사라지지 않고, 기사들이 모두 밀린 이후에 데미지를 입게 됨. 밀렸더라도 위치에 함정이 없으면 피해를 전혀 입지 않음.

Q번의 왕의 명령이 주어지게 됨. 생존한 기사들이 총 받은 데미지의 합 출력

해결 방법

밀고 피해 입히기밀린 기사들의 위치를 변경해주고, 밀린 기사들의 체력을 소모시켜줌.

for (int i = 1;i <= n;i++) {
    if (knight[i].pushed) {
        knight[i].r += dx[order[order_num].d], knight[i].c += dy[order[order_num].d];
    }
}
// 3. 밀린 기사들 피해 입히기
for (int ki = 1;ki <= n;ki++) {
    if (ki == k_n) continue;
    // 안밀렸거나 죽었으면 제외
    if (knight[ki].died || !knight[ki].pushed) continue;
    int h, w;
    h = knight[ki].h, w = knight[ki].w;
    x = knight[ki].r, y = knight[ki].c;
    int damage = 0;
    for (int i = 0;i < h;i++) {
        for (int j = 0;j < w;j++) {
            if (arr[x + i][y + j] == 1) {
                damage++;
            }
        }
    }
    knight[ki].cur_k = knight[ki].cur_k - damage;
    if (knight[ki].cur_k <= 0) {
        knight[ki].cur_k = 0;
        knight[ki].died = true;
    }
}

for (int i = 1;i <= n;i++) {
    knight[i].pushed = false;
}

기사가 이동할 수 있는지 확인기사의 벽을 다음 방향으로 이동하고, 다음 방향에 다른 기사가 있으면 해당 기사도 연쇄적으로 밀어줌. 만약 벽이랑 부딪히면, 밀 수 없음을 표시

void can_push(int k_n,int d) {
    int x, y, nx, ny,h,w;
    x = knight[k_n].r, y = knight[k_n].c;
    nx = x + dx[d], ny = y + dy[d];
    h = knight[k_n].h, w = knight[k_n].w;
    knight[k_n].pushed = true;
    visited[k_n] = 1;
    for (int i = 0;i < h;i++) {
        for (int j = 0;j < w;j++) {
            if (nx + i < 0 || nx + i >= l || ny + j < 0 || ny + j >= l) {
                can_push_flag = false; return;
            }
            if (arr[nx + i][ny + j] == 2) {
                can_push_flag = false; return;
            }
            if (tmp_knight_arr[nx + i][ny + j] != 0) {
                can_push_flag = false; return;
            }
            tmp_knight_arr[nx+i][ny+j] = k_n;
            if (knight_arr[nx+i][ny+j] > 0 && !visited[knight_arr[nx+i][ny+j]]) {
                visited[knight_arr[nx + i][ny + j]] = 1;
                can_push(knight_arr[nx + i][ny + j], d);
            }
        }
    }
}

전체 코드

#include <iostream>
#include <cstring>
using namespace std;

typedef struct {
    int r, c;
    int h, w;
    int k;
    int cur_k;
    bool died;
    bool pushed;
}_knight;

typedef struct {
    int i, d;
}_order;

int l, n, q;
int arr[42][42];
_knight knight[32];
_order order[101];

int knight_arr[42][42];

int tmp_knight_arr[42][42];
int visited[31];

// 위 오른쪽 아래 왼쪽
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

void input() {
    cin >> l >> n >> q;

    for (int i = 0;i < l;i++) {
        for (int j = 0;j < l;j++) {
            cin >> arr[i][j];
        }
    }

    for (int i = 1;i <= n;i++) {
        cin >> knight[i].r >> knight[i].c >> knight[i].h >> knight[i].w >> knight[i].k;
        knight[i].cur_k = knight[i].k;
        knight[i].r--; knight[i].c--;
        knight[i].died = false;
        knight[i].pushed = false;
    }

    for (int i = 0;i < q;i++) {
        cin >> order[i].i >> order[i].d;
    }

}

void set_knight_arr() {
    memset(knight_arr, 0, sizeof(knight_arr));
    int x, y, w,h;
    for (int kn = 1;kn <= n;kn++) {
        w = knight[kn].w, h = knight[kn].h;
        x = knight[kn].r, y = knight[kn].c;
        if (knight[kn].died) continue;
        for (int i = 0;i < h;i++) {
            for (int j = 0;j < w;j++) {
                knight_arr[x + i][y + j] = kn;
            }
        }
    }
}

bool can_push_flag = true;

void can_push(int k_n,int d) {
    int x, y, nx, ny,h,w;
    x = knight[k_n].r, y = knight[k_n].c;
    nx = x + dx[d], ny = y + dy[d];
    h = knight[k_n].h, w = knight[k_n].w;
    knight[k_n].pushed = true;
    visited[k_n] = 1;
    for (int i = 0;i < h;i++) {
        for (int j = 0;j < w;j++) {
            if (nx + i < 0 || nx + i >= l || ny + j < 0 || ny + j >= l) {
                can_push_flag = false; return;
            }
            if (arr[nx + i][ny + j] == 2) {
                can_push_flag = false; return;
            }
            if (tmp_knight_arr[nx + i][ny + j] != 0) {
                can_push_flag = false; return;
            }
            tmp_knight_arr[nx+i][ny+j] = k_n;
            if (knight_arr[nx+i][ny+j] > 0 && !visited[knight_arr[nx+i][ny+j]]) {
                visited[knight_arr[nx + i][ny + j]] = 1;
                can_push(knight_arr[nx + i][ny + j], d);
            }
        }
    }
}

void print_arr() {
    cout << "print_arr:\\n";
    for (int i = 0;i < l;i++) {
        for (int j = 0;j < l;j++) {
            if (arr[i][j] == 2) cout << "# ";
            else cout << knight_arr[i][j] << " ";
        }
        cout << "\\n";
    }
}

void solve(int order_num) {
    // i번 기사에게 d로 한칸 이동해라.
    int k_n = order[order_num].i;
    int x = knight[k_n].r;
    int y = knight[k_n].c;
    // 0. 죽었으면 그냥 넘기기
    if (knight[k_n].died) return;
    // 1. 밀 수 있는지 확인
    can_push_flag = true;
    memset(visited, 0, sizeof(visited));
    memset(tmp_knight_arr, 0, sizeof(tmp_knight_arr));
    can_push(k_n, order[order_num].d);
    if (can_push_flag == false) {
        for (int i = 1;i <= n;i++) {
            knight[i].pushed = false;
        }
        return;
    }

    // 2. 밀기
    for (int i = 1;i <= n;i++) {
        if (knight[i].pushed) {
            knight[i].r += dx[order[order_num].d], knight[i].c += dy[order[order_num].d];
        }
    }
    // 3. 밀린 기사들 피해 입히기
    for (int ki = 1;ki <= n;ki++) {
        if (ki == k_n) continue;
        // 안밀렸거나 죽었으면 제외
        if (knight[ki].died || !knight[ki].pushed) continue;
        int h, w;
        h = knight[ki].h, w = knight[ki].w;
        x = knight[ki].r, y = knight[ki].c;
        int damage = 0;
        for (int i = 0;i < h;i++) {
            for (int j = 0;j < w;j++) {
                if (arr[x + i][y + j] == 1) {
                    damage++;
                }
            }
        }
        knight[ki].cur_k = knight[ki].cur_k - damage;
        if (knight[ki].cur_k <= 0) {
            knight[ki].cur_k = 0;
            knight[ki].died = true;
        }
    }

    for (int i = 1;i <= n;i++) {
        knight[i].pushed = false;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
//    freopen("sample_input.txt", "r", stdin);

    input();
    for (int i = 0;i < q;i++) {
        set_knight_arr();
        solve(i);
    }

    int result = 0;
    for (int i = 1;i <= n;i++) {
        if (knight[i].died) continue;
        result += (knight[i].k - knight[i].cur_k);
    }

    cout << result;
    return 0;
}