[Code Tree] 삼성 SW 역량테스트 기출 풀이

취업 준비를 위한 코딩테스트를 손 놓은지 근 3년 만에

SSAFY 임직원 멘토링을 하려면 다시 기출은 풀 수준은 되어야 하지 않을까 싶어서

최근 기출 문제를 풀어봤다.

(입사 후 프로 등급도 취득했지만 알고리즘을 풀지 않은지 오래돼서 감이 떨어졌다)

 

라떼는 백준에 기출이 올라왔는데 이제는 code tree에 올라온다.

최신 기출이 상/하반기, 오전/오후 분류가 잘 되어있어서 실전 연습하기는 좋아보인다.

 

풀어본 문제는 2023 하반기 오전 1번 문제 "왕실의 기사 대결" 이다.

 

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

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

 

정사각형 L 의 격자판에서 기사의 움직임을 명령하는 구현 문제임을 확인했고,

기사가 다른 기사를 밀치고 연쇄반응이 일어난다는 것에서 dfs 혹은 bfs 를 사용해야 한다고 인지했다.

(dfs bfs 중 어느 것이 효율적일지는 끝까지 읽어보고 생각하면서 정하는 것이 후에 헷갈리지 않는다고 생각한다.)

 

구현 문제는 이른바 난이도 조절

문제를 어렵게 하기 위해 혹은 반례를 줄여주기 위해서 조건을 여러개 달아준다.

이 조건 하나를 빼먹게 되면 엣지 케이스에서 틀리거나,

쓸데없는 디버깅으로 시간을 낭비하게 된다.

 

그래서 꼼꼼히 읽어서 코딩 전에 function으로 나눌 수 있는 분기와 로직을 간단히 메모해두는 것이

실수해서 디버깅할 때 참고하기도 좋고,

코딩으로 옮기면서 빠트리지 않게 된다.

 

구현 문제는 글로 풀어져있는 로직을

얼마나 꼼꼼히 순서대로 코딩을 잘 해내는가에 달려있다.

 

어려운 문제라고 느낄때면 이 로직을 최대한 압축해서 (재귀나 반복문을 최소한으로 사용)

풀어져있는 function을 한번에 진행시킬때이다.

 

이 문제는 격자판 크기, 기사 수, 명령 수 등 부담이 없는 크기를 줬기 때문에

(실수를 줄이기 위해서라도)

 

그냥 시키는대로 코딩하는 것이 낫다고 판단했다.

 

이 문제에서 고민이 필요한 부분은

1. 밀기(연쇄)가 가능한 지 판단하는 로직

2. 밀기가 가능한 경우 대미지 계산

 

정도이다. 1번의 경우는 기사가 1x1 크기가 아니기 때문에 다음 밀려날 기사를 찾는 과정이 조금 귀찮다.

 

다음은 정답을 받은 풀이 코드다.

오랜만에 c++로 문제를 풀었기에 코드가 아주 깔끔하진 않다.

 

#include <iostream>
#include <unordered_set>

using namespace std;

int L, N, Q;
int board[41][41];
int knightBoard[41][41];
int dr[4] = { -1, 0, 1, 0 };
int dc[4] = { 0, 1, 0, -1 };
long long totalDamage = 0;

struct Knight {
    int r;
    int c;
    int h;
    int w;
    int k;
    int damage;
    bool alive;

    Knight() {}

    Knight(int r, int c, int h, int w, int k) {
        this->r = r;
        this->c = c;
        this->h = h;
        this->w = w;
        this->k = k;
        this->alive = true;
        this->damage = 0;
    }
} knights[31];

bool canMove(Knight knight, int d) {
    int sr = knight.r;
    int sc = knight.c;
    int er = sr + knight.h;
    int ec = sc + knight.w;

    for (int r = sr; r < er; r++) {
        for (int c = sc; c < ec; c++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (nr < 1 || nc < 1 || nr > L || nc > L) return false;
            if (board[nr][nc] == 2) return false;
        }
    }

    return true;
}

unordered_set<int> getKnightsNum(int n, int d) {
    Knight knight = knights[n];
    unordered_set<int> ret;
    int sr = knight.r;
    int sc = knight.c;
    int er = sr + knight.h;
    int ec = sc + knight.w;

    for (int r = sr; r < er; r++) {
        for (int c = sc; c < ec; c++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            if (nr < 1 || nc < 1 || nr > L || nc > L) continue;
            if (knightBoard[nr][nc] == n || knightBoard[nr][nc] == 0) continue;
            ret.insert(knightBoard[nr][nc]);
        }
    }

    return ret;
}

bool canPush(Knight knight, int d, int n) {
    bool ret = true;
    if (canMove(knight, d)) {
        unordered_set<int> pKnights = getKnightsNum(n, d);
        for (int i : pKnights) {
            Knight pKnight = knights[i];
            if (pKnight.alive == false) continue;
            ret = ret && canPush(pKnight, d, i);
        }
    }
    else {
        ret = false;
    }

    return ret;
}

void calculateDamage(int n, int d) {
    Knight knight = knights[n];
    int sr = knight.r;
    int sc = knight.c;
    int er = sr + knight.h;
    int ec = sc + knight.w;

    for (int r = sr; r < er; r++) {
        for (int c = sc; c < ec; c++) {
            if (board[r][c] == 1) knights[n].damage++;
        }
    }
    
    if (knights[n].k <= knights[n].damage) {
        for (int r = sr; r < er; r++) {
            for (int c = sc; c < ec; c++) {
                knightBoard[r][c] = 0;
                knights[n].alive = false;
            }
        }
    }
}

void move(int n, int d) {
    Knight knight = knights[n];

    int sr = knight.r;
    int sc = knight.c;
    int er = sr + knight.h;
    int ec = sc + knight.w;

    for (int r = sr; r < er; r++) {
        for (int c = sc; c < ec; c++) {
            knightBoard[r][c] = 0;
        }
    }

    knights[n].r += dr[d];
    knights[n].c += dc[d];

    knight = knights[n];

    sr = knight.r;
    sc = knight.c;
    er = sr + knight.h;
    ec = sc + knight.w;

    for (int r = sr; r < er; r++) {
        for (int c = sc; c < ec; c++) {
            knightBoard[r][c] = n;
        }
    }
}

void push(int n, int d, int depth) {
    unordered_set<int> pKnights = getKnightsNum(n, d);
    for (int i : pKnights) {
        Knight pKnight = knights[i];
        push(i, d, depth + 1);
    }
    move(n, d);
    if (depth != 0) {
        calculateDamage(n, d);
    }
}

int main() {
    cin >> L >> N >> Q;
    
    for (int r = 1; r <= L; r++) {
        for (int c = 1; c <= L; c++) {
            cin >> board[r][c];
        }
    }

    for (int n = 1; n <= N; n++) {
        int r, c, h, w, k;
        cin >> r >> c >> h >> w >> k;
        knights[n] = Knight(r, c, h, w, k);
        for (int i = r; i < r + h; i++) {
            for (int j = c; j < c + w; j++) {
                knightBoard[i][j] = n;
            }
        }
    }

    for (int q = 0; q < Q; q++) {
        int n, d;
        cin >> n >> d;

        if (knights[n].alive == false) continue;
        if (canPush(knights[n], d, n)) {
            push(n, d, 0);
        }
    }

    for (int n = 1; n <= N; n++) {
        if (knights[n].alive) totalDamage += knights[n].damage;
    }

    cout << totalDamage << "\n";

    return 0;
}

 

후기 :

처음에 안일하고 만만하게 문제를 읽어 놓친 부분이 많았고 때문에 시간이 오래 걸렸다.

조건이 타이트하지 않기 때문에 그저 구현만 하는 것으로도 시간초과가 되지 않았다.

'살아남은 기사' 들의 대미지를 계산하는 몇 글자를 빠트리고 읽는 실수가 있었는데

취준할 때 제일 경계하던 것이다.

 

21년 마지막 기출을 풀었던 기억으로 난이도를 평가하자면,

크게 어렵진 않으나 꼼꼼히 풀 필요가 있는 정도이다.

사용된 알고리즘은 dfs, 사용한 라이브러리는 unordered_set (dfs 사용해서 기사 번호를 중복되지 않게 리턴 받기 위함)

dfs를 따로 두 번 돌려도 시간초과가 걸리지 않았음.

 

혹시 이 글을 읽는 취준생분들이 계시다면 절대로 한글자도 빠트리지 않고 정독하는 습관이

소중한 디버깅 시간을 줄여줄 수 있다는 점을 참고하시면 좋겠다.