[코드트리_삼성기출] 왕실의 기사 대결 (C++)

[아이디어]

단순 구현으로 해결했습니다.

 

[요약]

i) 기사 이동 방법

왕의 기사와 방향을 명령을 내림

해당 기사는 상하좌우로 이동

if ( 이동할 위치에 다른 기사가 있다면 ) 해당 기사도 연쇄적으로 밀림

if ( 벽이 있다면 ) 이동 불가

if ( 명령 내릴 기사가 없다면 ) 어떤 작업도 시작되지 않음

 

ii) 대결 대미지

명령 받은 기사가 다른 기사 밀면 "밀려난"기사는 피해를 입는다.

명령 받은기사는 어떤 피해도 없다.

기사가 "모두 밀린" 뒤 대미지를 입는다.

각 기사가 "이동한 위치"에서 (r,c) 좌상단을 기준으로 h x w의 영역 내에 함정 수만큼 피해를 입음

if ( 현재체력 < 피해 입을 체력 ) 기사는 체스판에서 사라짐

 

 

[방법]

for ( 왕의 명령 수만큼 반복 )
    if ( 기사가 체스판위에 아직 있는지 확인 ) 없다면 pass
    
    기사 위치를 백업 (knigh_map) // (tmp_knight_map 을 활용해 기사 이동 가능여부 판단)
    
    if ( 이동할 수 있는지(기사번호, 이동방향) ) 이동할 수 없다면 pass
    
    기사 위치 갱신 (tmp_knight_map -> knight_map)
    
    기사 정보(좌표, 피해량) 갱신

 

이동할 수 있는지 판단하는 함수를 재귀호출로 구현.

왕의 명령 -> 해당 기사의 이동 가능 여부 판단 -> 다른 기사가 있다면 -> 다른 기사의 이동 가능 여부 판단 -> ...

왕의 명령 -> 해당 기사의 이동 가능 여부 판단 -> 벽이 있다면 -> 재귀를 빠져나옴

 

[설명]

can_move_knight(기사 번호, 이동 방향)

기사의 이동 가능여부를 판단하고

이동이 가능한 기사에 한해 기사 이동

bool can_move_knight(int num, int dir) { // 기사번호, 방향
    KNIGHT* now = &knights[num];
    int ny = now->r + dy[dir];
    int nx = now->c + dx[dir];

    if ((ny < 1) || ((ny + now->h - 1) > L) || (nx < 1) || ((nx + now->w - 1) > L)) return false; // 영역을 벗어남

    FOR(y, ny, (ny + now->h)) {
        FOR(x, nx, (nx + now->w)) {
            if (map[y][x] == 2) return false; // 벽에 막힘
        }
    }

    FOR(y, ny, (ny + now->h)) {
        FOR(x, nx, (nx + now->w)) {
            if ((knight_map[y][x] != 0) && (knight_map[y][x] != num)) { // 자신이 아닌 다른 기사가 있음
                if (can_move_knight(knight_map[y][x], dir) == false) return false; // 다른 기사가 이동 못함
            }
        }
    }

    move_knight(num, dir); // 기사 이동

    return true;
}

 

update_knight_info(기사 번호)

기사가 이동한 위치, 피해량 갱신

void update_knight_info(int num) {
    bool visit[KNIGHTS_MAX] = { 0, };

    FOR(y, 1, (L + 1)) { // 좌표 갱신
        FOR(x, 1, (L + 1)) {
            int now = knight_map[y][x];
            if (now == 0) continue;
            if (visit[now] == true) continue;
            visit[now] = true;


            if (knights[now].k <= 0) continue; // 이미 체스판에서 사라진 기사
            if (knights[now].r != y || knights[now].c != x) knights[now].isMove = true; // 기사의 이동여부 플래그처리
            knights[now].r = y;
            knights[now].c = x;
        }
    }

    FOR(i, 1, (N + 1)) { // 피해계산
        KNIGHT* now = &knights[i];
        if (now->isMove == false) continue; // 이동한적 없는 기사라면
        now->isMove = false;
        if (i == num) continue; // 명령받은 기사
        if (now->k <= 0) continue; // 이미 체스판에서 사라진 기사

        int trap_cnt = 0;
        FOR(y, now->r, (now->r + now->h)) {
            FOR(x, now->c, (now->c + now->w)) {
                if (map[y][x] == 1) ++trap_cnt;
            }
        }

        now->k -= trap_cnt;
        now->damage_sum += trap_cnt;

        if (now->k <= 0) { // 체력이 0이하가 되면 체스판에서 사라짐
            FOR(y, now->r, (now->r + now->h)) {
                FOR(x, now->c, (now->c + now->w)) {
                    knight_map[y][x] = 0;
                }
            }
        }
    }
}

 

[회고]

테스트케이스 3번에서 막혔었습니다.

test_case_3.txt

0.00MB

 

문제 원인)

위 테스트 케이스에서 23번째 왕의 명령에서 오류를 발견함.

2번 기사에게 이동을 명령하고 2번기사만 이동을 하였는데, 

1번기사도 이동했다고 플래그처리가 있었음.

 

해결 방법)

피해량을 계산하는 로직을 처리하던 중

 

기존에

왕의 명령받은 기사인지, 체스판에서 사라진 기사인지 판별 후

isMove변수로 이동여부를 확인해 이동했던 기사인지 확인하고 isMove를 다시 false로 초기화해주었었습니다.

if (i == num) continue; // 명령받은 기사
if (now->k <= 0) continue; // 이미 체스판에서 사라진 기사
if (now->isMove == false) continue; // 이동한적 없는 기사라면
now->isMove = false;

 

이렇게 처리하니

선행조건에서 판별되어버려

이전의 기록이 초기화되지 않은채 다음 로직으로 넘어가 발생하는 문제였습니다.

그래서 조건의 판별 순서를 바꿔

isMove변수로 이동여부를 확인해 이동했던 기사인지 확인하고 isMove를 다시 false로 초기화 한 후,

왕의 명령을 받은 기사인지, 체스판에서 사라진 기사인지 판별해 주었습니다.

 

참고) 전체코드 중 Line number (118 ~ 121)

if (now->isMove == false) continue; // 이동한적 없는 기사라면
now->isMove = false;
if (i == num) continue; // 명령받은 기사
if (now->k <= 0) continue; // 이미 체스판에서 사라진 기사

[코드]

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

#define FOR(i,s,e) for(int i=s; i<e; ++i)
#define L_MAX (40 + 1)
#define KNIGHTS_MAX (30 + 1)
#define KING_CMD_NUM 100

int L, N, Q;
int map[L_MAX][L_MAX]; // 지도 ( 0: 빈칸, 1: 함정, 2: 벽 )
int knight_map[L_MAX][L_MAX]; // 기사배치
int tmp_knight_map[L_MAX][L_MAX]; // 기사위치를 백업해둘 변수
struct KNIGHT {
    int r, c, h, w, k;
    int damage_sum; // 피해의 합을 기록
    bool isMove; // 기사가 해당 턴에 밀렸었는지 기록
};
KNIGHT knights[KNIGHTS_MAX]; // 기사들의 정보 저장
struct KING {
    int i, d;
};
KING commands[KING_CMD_NUM]; // 왕의 명령들 저장
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };

void input() {
    cin >> L >> N >> Q;
    FOR(y, 1, (L + 1)) {
        FOR(x, 1, (L + 1)) {
            cin >> map[y][x];
        }
    }
    FOR(i, 1, (N + 1)) {
        KNIGHT* now = &knights[i];
        cin >> now->r >> now->c >> now->h >> now->w >> now->k;

        FOR(y, now->r, (now->r + now->h)) {
            FOR(x, now->c, (now->c + now->w)) {
                knight_map[y][x] = i;
            }
        }
    }
    FOR(i, 0, Q) {
        KING* now = &commands[i];
        cin >> now->i >> now->d;
    }
}

void move_knight(int num, int dir) {
    KNIGHT* now = &knights[num];
    int ny = now->r + dy[dir];
    int nx = now->c + dx[dir];

    FOR(y, now->r, (now->r + now->h)) {
        FOR(x, now->c, (now->c + now->w)) {
            if (tmp_knight_map[y][x] == num) {
                tmp_knight_map[y][x] = 0;
            }
        }
    }

    FOR(y, ny, (ny + now->h)) {
        FOR(x, nx, (nx + now->w)) {
            if (tmp_knight_map[y][x] == 0) {
                tmp_knight_map[y][x] = num;
            }
        }
    }
}

bool can_move_knight(int num, int dir) { // 기사번호, 방향
    KNIGHT* now = &knights[num];
    int ny = now->r + dy[dir];
    int nx = now->c + dx[dir];

    if ((ny < 1) || ((ny + now->h - 1) > L) || (nx < 1) || ((nx + now->w - 1) > L)) return false; // 영역을 벗어남

    FOR(y, ny, (ny + now->h)) {
        FOR(x, nx, (nx + now->w)) {
            if (map[y][x] == 2) return false; // 벽에 막힘
        }
    }

    FOR(y, ny, (ny + now->h)) {
        FOR(x, nx, (nx + now->w)) {
            if ((knight_map[y][x] != 0) && (knight_map[y][x] != num)) { // 자신이 아닌 다른 기사가 있음
                if (can_move_knight(knight_map[y][x], dir) == false) return false; // 다른 기사가 이동 못함
            }
        }
    }

    move_knight(num, dir); // 기사 이동

    return true;
}

void update_knight_info(int num) {
    bool visit[KNIGHTS_MAX] = { 0, };

    FOR(y, 1, (L + 1)) { // 좌표 갱신
        FOR(x, 1, (L + 1)) {
            int now = knight_map[y][x];
            if (now == 0) continue;
            if (visit[now] == true) continue;
            visit[now] = true;


            if (knights[now].k <= 0) continue; // 이미 체스판에서 사라진 기사
            if (knights[now].r != y || knights[now].c != x) knights[now].isMove = true; // 기사의 이동여부 플래그처리
            knights[now].r = y;
            knights[now].c = x;
        }
    }

    FOR(i, 1, (N + 1)) { // 피해계산
        KNIGHT* now = &knights[i];
        if (now->isMove == false) continue; // 이동한적 없는 기사라면
        now->isMove = false;
        if (i == num) continue; // 명령받은 기사
        if (now->k <= 0) continue; // 이미 체스판에서 사라진 기사

        int trap_cnt = 0;
        FOR(y, now->r, (now->r + now->h)) {
            FOR(x, now->c, (now->c + now->w)) {
                if (map[y][x] == 1) ++trap_cnt;
            }
        }

        now->k -= trap_cnt;
        now->damage_sum += trap_cnt;

        if (now->k <= 0) { // 체력이 0이하가 되면 체스판에서 사라짐
            FOR(y, now->r, (now->r + now->h)) {
                FOR(x, now->c, (now->c + now->w)) {
                    knight_map[y][x] = 0;
                }
            }
        }
    }
}

void sol() {
    FOR(cmd_num, 0, Q) {
        if (knights[commands[cmd_num].i].k <= 0) continue; // 체스판에서 사라진 기사
        memcpy(tmp_knight_map, knight_map, sizeof(knight_map)); // 백업
        if (can_move_knight(commands[cmd_num].i, commands[cmd_num].d) == false) {
            continue; // 명령 받은 기사가 움직일 수 있는지
        }
        memcpy(knight_map, tmp_knight_map, sizeof(knight_map)); // 갱신
        update_knight_info(commands[cmd_num].i);
    }

    int ans = 0;
    FOR(i, 1, (N + 1)) {
        KNIGHT* now = &knights[i];
        if (now->k <= 0) continue;

        ans += now->damage_sum;
    }

    cout << ans;
}

int main() {
    // 여기에 코드를 작성해주세요.
    freopen("input.txt", "r", stdin);

    input();
    sol();

    return 0;
}

 

[문제 출처]

https://www.codetree.ai/training-field/frequent-problems/problems/royal-knight-duel/description?page=1&pageSize=20