문제 링크

삼성 코딩테스트 기출 문제: 메두사와 전사들 - 코드트리

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

코드트리

문제 설명

N*N 크기의 배열 → 움직일 수 있는 곳 0, 아닌 곳 1 메두사의 좌표 S_r, S_c, 공원(도착지)의 좌표 E_r, E_c M명의 전사(방해물) (r_i,c_i)에 위치, 각 턴마다 메두사를 향해 이동(도로 아닌 곳도 가능)

1. 메두사의 이동최단 경로를 따라 메두사가 이동. 이동한 위치에 전사가 있다면 제거 (상 하 좌 우의 우선순위로 이동)
2. 메두사의 시선상 하 좌 우의 방향을 선택해서 바라봄. 시야각에 들어와있지만 다른 전사(방해물)에 가려져 있는 경우 보이지 않음. 시선 안에 위치한 전사(방해물)은 해당 턴에 움직일 수 없음. (같은 위치에 여러 명의 전사(방해물)이 있을 수 있음.) 전사(방해물)을 가장 많이 볼 수 있는 방향으로 바라보며, 같은 수가 여러개라면 상 하 좌 우로 우선순위
3. 전사 이동메두사와 가까워지는 방향으로 두번 이동. 격자 밖으로 나갈 수 없고, 메두사의 시야로는 이동할 수 없음. 첫 번째 이동에는 상 하 좌 우의 우선순위이고, 두 번째 이동에는 좌 우 상 하의 우선순위. 메두사의 위치에 도달한 전사는 사망
4. 출력물각 턴마다 모든 전사가 이동한 거리의 합, 메두사로 인해 돌로 변한 전사의 수, 메두사가 공격한 전사의 수를 출력

해결 방법

전사들 이동 및 공격

for (int i = 0;i < m;i++) {
    if (warrior[i].died || warrior[i].stone) continue;
    warrior_move_cnt += warrior_move(i, path[p].x, path[p].y,true);
    warrior_move_cnt += warrior_move(i, path[p].x, path[p].y,false);
}

2번 이동하는데, 상하좌우의 우선순위가 다르기 때문에, bool 값으로 다르게 설정해준다.

int warrior_move(int cur, int mx,int my, bool is_first) {
    int dx[4], dy[4];
    if (is_first) {
        dx[0] = -1, dx[1] = 1, dx[2] = 0, dx[3] = 0;
        dy[0] = 0, dy[1] = 0, dy[2] = -1, dy[3] = 1;
    }
    else {
        dx[2] = -1, dx[3] = 1, dx[0] = 0, dx[1] = 0;
        dy[2] = 0, dy[3] = 0, dy[0] = -1, dy[1] = 1;
    }

    int cx, cy, nx, ny;
    cx = warrior[cur].x, cy = warrior[cur].y;
    int cur_distance = abs(mx - cx) + abs(my - cy);
    int next_distance = 987654321;
    int nd = -1;
    for (int d = 0;d < 4;d++) {
        int tmp_distance;
        nx = cx + dx[d], ny = cy + dy[d];
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
        if (sight_arr[nx][ny] == 1) continue;
        tmp_distance = abs(mx - nx) + abs(my - ny);
        if (tmp_distance >= cur_distance || tmp_distance >= next_distance) continue;
        next_distance = tmp_distance;
        nd = d;
    }

    if (nd == -1) return 0;
    warrior[cur].x += dx[nd], warrior[cur].y += dy[nd];
    return 1;
}

메두사가 병사를 돌로 만드는 함수에서 미리 선언한 sight_arr를 활용하여, 해당 병사가 메두사의 시야에 있는지, 격자를 벗어나는지 확인하고 최단거리를 계산해서 돌려준다.

int died_count = 0;
for (int i = 0;i < m;i++) {            
    if (warrior[i].x == path[p].x && warrior[i].y == path[p].y && !warrior[i].died && !warrior[i].stone) {
        warrior[i].died = true;
        died_count++;
    }
    warrior[i].stone = false;
}

이동한 병사들의 위치를 확인하여 메두사와 같은 위치라면 죽음으로 변경하고, 출력을 위하여 died_count 변수에 죽은 인원을 추가한다.

가장 많은 전사를 바라볼 수 있는 시야 선정 및 돌로 만들기

int d = -1; int stone_chk = 0;
for (int i = 0;i < 4;i++) {
    int cur_val = medu_sight(i, path[p].x, path[p].y,false);
    if (cur_val > stone_chk) {
        d = i, stone_chk = cur_val;
    }
}

medu_sight 함수를 이용하여, 각 위치에서 메두사가 봐야 할 방향을 d에 저장하고, 출력을 위한 돌로 된 병사들의 수를 stone_chk에 저장한다.

int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };
memset(marr, 0, sizeof(marr));

// 1. 병사들 위치 체크
for (int i = 0;i < m;i++) {
    if (warrior[i].died) continue;
    marr[warrior[i].x][warrior[i].y]++;
}

// 메두사 시야 설정을 위한 변수
int cnt = 1;
int s, e;
int ret = 0;

if (d == 0) { // 상단
    for (int i = x - 1;i >= 0;i--) {
        s = y - cnt < 0 ? 0 : y - cnt;
        e = y + cnt >= n ? n - 1 : y + cnt;
        for (int j = s;j <= e;j++) {
            if (real_flag && sight_arr[i][j] != -1) sight_arr[i][j] = 1;
            if (marr[i][j] > 0) { // 병사가 있다면
                set_war_back(i, j, x, y, d,real_flag);
                ret += marr[i][j];                    
                marr[i][j] = 999;
            }
        }
        cnt++;
    }
}

쉬운 조건 탐색을 위해, 우선 marr 배열에 병사의 위치를 표시해놓는다. 메두사는 이등변삼각형 모양의 시야를 갖기 때문에, 이중 배열 및 추가 변수를 활용하여 메두사가 볼 수 있는 병사들을 체크한다. 만약, 메두사가 병사를 발견하면 해당 위치의 marr의 값을 999로 변경하고, 사각 지대(해당 병사의 뒤)를 set_war_back 함수를 통해 음수로 변경한다.

int wloc;
int cnt = 1;
int s, e;
if (d == 0) {
    wloc = my - y;
    for (int i = x - 1;i >= 0;i--) {
        if (wloc > 0) {
            s = y - cnt < 0 ? 0 : y - cnt;
            e = y;
        }
        else if (wloc < 0) {
            s = y;
            e = y + cnt >= n ? n - 1 : y + cnt;
        }
        else {
            s = y, e = y;
        }
        for (int j = s;j <= e;j++) {
            marr[i][j] = -1;
            if (real_flag) sight_arr[i][j] = -1;
        }
        cnt++;
    }
}

wloc을 방향 당 조건으로 설정한다. (wloc이 양수이면 좌측, 0이면 뒤에만, 음수면 우측 … 이런식으로) 해당 조건을 활용하여, 병사 뒤의 값들을 -1로 변경한다.

    if (real_flag) {
        for (int i = 0;i < m;i++) {
            if (marr[warrior[i].x][warrior[i].y] == 999) {
                warrior[i].stone = true;
            }
        }
    }

    return ret;

d를 얻고 나면, real_flag 인자를 true로 넣어 999(발각된 병사들)의 위치에 해당하는 병사들의 stone 여부를 true로 변경한다.

메두사의 이동경로 저장get_path 함수에 해당하는 과정임.

queue<pair<int, int>> que;
que.push({ start[0],start[1] });
visited[start[0]][start[1]] = 1;

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

bool found = false;

int cx, cy;
while (!que.empty()) {
    tie(cx, cy) = que.front();
    que.pop();
    
    if (cx == dest[0] && cy == dest[1]) {
        found = true;
        break;
    }

    for (int i = 0;i < 4;i++) {
        int nx, ny;
        nx = cx + dx[i], ny = cy + dy[i];
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
        if (visited[nx][ny] || arr[nx][ny]) continue;
        visited[nx][ny] = 1;
        parent[nx][ny][0] = cx, parent[nx][ny][1] = cy;
        que.push({ nx,ny });
    }
}

if (!found) return false;

BFS를 활용해서 start에서 dest까지의 경로를 parent배열에 저장

cx = dest[0], cy = dest[1];

while (!(cx == start[0] && cy == start[1])) {
    _loc tmp;
    tmp.x = cx, tmp.y = cy;
    path.push_back(tmp);
    cx = parent[tmp.x][tmp.y][0], cy = parent[tmp.x][tmp.y][1];
}

reverse(path.begin(), path.end());

return true;

dest에서부터 parent 배열을 활용하여 이전 경로를 하나하나씩 탐색해가며 경로를 path 벡터에 저장한다. 저장 후, path배열을 reverse를 활용하여 돌려준다.

for (int p = 0;p < path.size() - 1;p++) {
		...
    cout << warrior_move_cnt << " " << stone_chk << " " << died_count << "\\n";
}

그리고 해당 경로 벡터를 활용하여, 아래의 절차들을 반복해준다.

전체 코드

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

typedef struct {
    int x, y;
}_loc;

typedef struct {
    int x, y;
    bool died;
    bool stone;
}_war;
int n, m;
int start[2];
int dest[2];
_war warrior[301];
int arr[51][51];

vector<_loc> path;

void input() {
    cin >> n >> m;

    cin >> start[0] >> start[1] >> dest[0] >> dest[1];

    for (int i = 0;i < m;i++) {
        cin >> warrior[i].x >> warrior[i].y;
        warrior[i].died = false;
        warrior[i].stone = false;
    }

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

int visited[51][51];
int parent[51][51][2];
bool get_path() {
    queue<pair<int, int>> que;
    que.push({ start[0],start[1] });
    visited[start[0]][start[1]] = 1;

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

    bool found = false;

    int cx, cy;
    while (!que.empty()) {
        tie(cx, cy) = que.front();
        que.pop();
        
        if (cx == dest[0] && cy == dest[1]) {
            found = true;
            break;
        }

        for (int i = 0;i < 4;i++) {
            int nx, ny;
            nx = cx + dx[i], ny = cy + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
            if (visited[nx][ny] || arr[nx][ny]) continue;
            visited[nx][ny] = 1;
            parent[nx][ny][0] = cx, parent[nx][ny][1] = cy;
            que.push({ nx,ny });
        }
    }

    if (!found) return false;

    cx = dest[0], cy = dest[1];

    while (!(cx == start[0] && cy == start[1])) {
        _loc tmp;
        tmp.x = cx, tmp.y = cy;
        path.push_back(tmp);
        cx = parent[tmp.x][tmp.y][0], cy = parent[tmp.x][tmp.y][1];
    }

    reverse(path.begin(), path.end());

    return true;
}

int marr[51][51];
int sight_arr[51][51];

void set_war_back(int x, int y, int mx, int my, int d,bool real_flag) {
    int wloc;
    int cnt = 1;
    int s, e;
    if (d == 0) {
        wloc = my - y;
        for (int i = x - 1;i >= 0;i--) {
            if (wloc > 0) {
                s = y - cnt < 0 ? 0 : y - cnt;
                e = y;
            }
            else if (wloc < 0) {
                s = y;
                e = y + cnt >= n ? n - 1 : y + cnt;
            }
            else {
                s = y, e = y;
            }
            for (int j = s;j <= e;j++) {
                marr[i][j] = -1;
                if (real_flag) sight_arr[i][j] = -1;
            }
            cnt++;
        }
    }
    else if (d == 1) {
        wloc = my - y;
        for (int i = x + 1;i<n;i++) {
            if (wloc > 0) {
                s = y - cnt < 0 ? 0 : y - cnt;
                e = y;
            }
            else if (wloc < 0) {
                s = y;
                e = y + cnt >= n ? n - 1 : y + cnt;
            }
            else {
                s = y, e = y;
            }
            for (int j = s;j <= e;j++) {
                marr[i][j] = -1;
                if (real_flag) sight_arr[i][j] = -1;
            }
            cnt++;
        }
    }
    else if (d == 2) {
        wloc = mx - x;
        for (int i = y - 1;i >= 0;i--) {
            if (wloc > 0) {
                s = x - cnt < 0 ? 0 : x - cnt;
                e = x;
            }
            else if (wloc < 0) {
                s = x;
                e = x + cnt >= n ? n - 1 : x + cnt;
            }
            else {
                s = x, e = x;
            }
            for (int j = s;j <= e;j++) {
                marr[j][i] = -1;
                if (real_flag) sight_arr[j][i] = -1;
            }
            cnt++;
        }
    }
    else {
        wloc = mx - x;
        for (int i = y + 1;i < n;i++) {
            if (wloc > 0) {
                s = x - cnt < 0 ? 0 : x - cnt;
                e = x;
            }
            else if (wloc < 0) {
                s = x;
                e = x + cnt >= n ? n - 1 : x + cnt;
            }
            else {
                s = x, e = x;
            }
            for (int j = s;j <= e;j++) {
                marr[j][i] = -1;
                if (real_flag) sight_arr[j][i] = -1;
            }
            cnt++;
        }
    }
}

int medu_sight(int d,int x,int y,bool real_flag) { // 상,하,좌,우
    int dx[4] = { -1,1,0,0 };
    int dy[4] = { 0,0,-1,1 };
    memset(marr, 0, sizeof(marr));

    // 1. 병사들 위치 체크
    for (int i = 0;i < m;i++) {
        if (warrior[i].died) continue;
        marr[warrior[i].x][warrior[i].y]++;
    }

    // 메두사 시야 설정을 위한 변수
    int cnt = 1;
    int s, e;
    int ret = 0;

    if (d == 0) {
        for (int i = x - 1;i >= 0;i--) {
            s = y - cnt < 0 ? 0 : y - cnt;
            e = y + cnt >= n ? n - 1 : y + cnt;
            for (int j = s;j <= e;j++) {
                if (real_flag && sight_arr[i][j] != -1) sight_arr[i][j] = 1;
                if (marr[i][j] > 0) { // 병사가 있다면
                    set_war_back(i, j, x, y, d,real_flag);
                    ret += marr[i][j];                    
                    marr[i][j] = 999;
                }
            }
            cnt++;
        }
    }
    else if (d == 1) {
        for (int i = x + 1;i < n;i++) {
            s = y - cnt < 0 ? 0 : y - cnt;
            e = y + cnt >= n ? n - 1 : y + cnt;
            for (int j = s;j <= e;j++) {
                if (real_flag && sight_arr[i][j] != -1) sight_arr[i][j] = 1;
                if (marr[i][j] > 0) { // 병사가 있다면
                    set_war_back(i, j, x, y, d,real_flag);
                    ret += marr[i][j];
                    marr[i][j] = 999;
                }
            }
            cnt++;
        }
    }
    else if (d == 2) {
        for (int i = y - 1;i >= 0;i--) {
            s = x - cnt < 0 ? 0 : x - cnt;
            e = x + cnt >= n ? n - 1 : x + cnt;
            for (int j = s;j <= e;j++) {
                if (real_flag && sight_arr[j][i] != -1) sight_arr[j][i] = 1;
                if (marr[j][i] > 0) { // 병사가 있다면
                    set_war_back(j, i, x, y, d,real_flag);
                    ret += marr[j][i];
                    marr[j][i] = 999;
                }
            }
            cnt++;
        }
    }
    else {
        for (int i = y + 1;i < n;i++) {
            s = x - cnt < 0 ? 0 : x - cnt;
            e = x + cnt >= n ? n - 1 : x + cnt;
            for (int j = s;j <= e;j++) {
                if (real_flag && sight_arr[j][i] != -1) sight_arr[j][i] = 1;
                if (marr[j][i] > 0) { // 병사가 있다면
                    set_war_back(j, i, x, y, d,real_flag);
                    ret += marr[j][i];
                    marr[j][i] = 999;
                }
            }
            cnt++;
        }
    }

    if (real_flag) {
        for (int i = 0;i < m;i++) {
            if (marr[warrior[i].x][warrior[i].y] == 999) {
                warrior[i].stone = true;
            }
        }
    }

    return ret;
}

int warrior_move(int cur, int mx,int my, bool is_first) {
    int dx[4], dy[4];
    if (is_first) {
        dx[0] = -1, dx[1] = 1, dx[2] = 0, dx[3] = 0;
        dy[0] = 0, dy[1] = 0, dy[2] = -1, dy[3] = 1;
    }
    else {
        dx[2] = -1, dx[3] = 1, dx[0] = 0, dx[1] = 0;
        dy[2] = 0, dy[3] = 0, dy[0] = -1, dy[1] = 1;
    }

    int cx, cy, nx, ny;
    cx = warrior[cur].x, cy = warrior[cur].y;
    int cur_distance = abs(mx - cx) + abs(my - cy);
    int next_distance = 987654321;
    int nd = -1;
    for (int d = 0;d < 4;d++) {
        int tmp_distance;
        nx = cx + dx[d], ny = cy + dy[d];
        if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
        if (sight_arr[nx][ny] == 1) continue;
        tmp_distance = abs(mx - nx) + abs(my - ny);
        if (tmp_distance >= cur_distance || tmp_distance >= next_distance) continue;
        next_distance = tmp_distance;
        nd = d;
    }

    if (nd == -1) return 0;
    warrior[cur].x += dx[nd], warrior[cur].y += dy[nd];
    return 1;
}

int solve() {
    if (!get_path()) return -1;

    for (int p = 0;p < path.size() - 1;p++) {
        // 모든 전사가 이동한 거리의 합 , 메두사로 인해 돌이 된 전사의 수 , 메두사를 공격한 전사의 수
        // 이동한 위치에 전사가 있으면 죽이기
        for (int i = 0;i < m;i++) {
            if (warrior[i].x == path[p].x && warrior[i].y == path[p].y && warrior[i].died == false) {
                warrior[i].died = true;
            }
        }
        // 1. 메두사의 시선
        // 1-1. 메두사가 볼 시선을 정함
        int d = -1; int stone_chk = 0;
        for (int i = 0;i < 4;i++) {
            int cur_val = medu_sight(i, path[p].x, path[p].y,false);
            if (cur_val > stone_chk) {
                d = i, stone_chk = cur_val;
            }
        }

        // 2. 메두사가 병사들은 돌로 만듬
        memset(sight_arr, 0, sizeof(sight_arr));
        medu_sight(d, path[p].x, path[p].y,true);

        // 3. 전사들의 이동
        int warrior_move_cnt = 0;
        for (int i = 0;i < m;i++) {
            if (warrior[i].died || warrior[i].stone) continue;
            warrior_move_cnt += warrior_move(i, path[p].x, path[p].y,true);
            warrior_move_cnt += warrior_move(i, path[p].x, path[p].y,false);
        }

        // 4. 전사들의 공격 + 돌로 변한 전사들 풀어주기
        int died_count = 0;
        for (int i = 0;i < m;i++) {            
            if (warrior[i].x == path[p].x && warrior[i].y == path[p].y && !warrior[i].died && !warrior[i].stone) {
                warrior[i].died = true;
                died_count++;
            }
            warrior[i].stone = false;
        }

        cout << warrior_move_cnt << " " << stone_chk << " " << died_count << "\\n";
    }

    return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    input();
    cout << solve();
}