포탑 부수기

https://www.codetree.ai/training-field/frequent-problems/problems/destroy-the-turret/description?page=1&pageSize=20 

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

1. 최단 거리이므로 BFS를 쓰자.

split_damage를 위해서는

BFS의 경로를 이용!

경로를 저장하는 배열을 만들어 경로를 저장해가면서 BFS를 진행!

숨바꼭질 문제, DSLR 문제에서 풀었다.

 

우/하/좌/상의 우선순위대로 먼저 움직인 경로가 선택되므로

dx[], dy[]도 우/하/좌/상 순으로 만든다.

 

실수!

공격하는 타워 좌표를 dx, dy로 놓았다가

위의 배열과 충돌이 일어났었다. 

변수 설정 조심하자!

 

2. 맵이 이어질 때 nx, ny 처리법

가장자리에서 막힌 방향으로 진행하고자 한다면, 반대편으로 나옵니다.

https://larc-en-ciel.tistory.com/206

마법사 상어와 파이어볼 + 비바라기

파이어볼 문제에서 배웠다. 모둘러 연산을 이용한다.

 

int nx = (x + dx[k] + n) % n;
int ny = (y + dy[k] + m) % m;

 

n과 m을 더해주고 % 연산을 해주면 된다.

 

3. 시간 초과가 나왔다.

Reason 1. 맨 처음 풀이는 삼중 for문을 이용했었다.

map의 이중 포문 안에서 하나하나 tower의 row, col과 비교하는 미친 짓을 했다.

왜? 시간이라는 변수가 있으니..

 

하지만 간단하게 해결 가능했다.

int rec[15][15];

시간 기록 이차원 배열을 만들어서

tower.clear()를 한 다음

map 값이랑 rec 값을 tower에 넣어주면 됐다!

공격자 포탑은

rec[tower[0].row][tower[0].col] = t;

 

Reason 2.

BFS 경로를 저장할 때 이차원 벡터에 pair를 넣어서 사용했다.

매우 시간이 오래 걸렸다. 

그냥 x 좌표용 이차원 배열, y 좌표용 이차원 배열을 만드니 

시간 초과가 해결 되었다.

 

<소스코드>

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
 
int canon_x[] = { -1,-1, -1, 0, 0, 1,1, 1 };
int canon_y[] = { -1,0, 1, -1, 1, -1, 0, 1 };
 
int map[15][15];
int rec[15][15];
bool visited[15][15];
 
// 공격과 관련이 있었는가를 체크
bool related[15][15];
 
int back_x[15][15];
int back_y[15][15];
 
int n, m, k;
 
struct t_info
{
    int row;
    int col;
    int jikan;
    int power;
};
 
// sort에서는 반대
bool operator < (const t_info& a, const t_info& b)
{
    if (a.power == b.power)
    {
        if (a.jikan == b.jikan)
        {
            if ((a.row + a.col) == (b.row + b.col))
            {
                return a.col > b.col;
            }
            return (a.row + a.col) > (b.row + b.col);
        }
        return a.jikan > b.jikan;
    }
    return a.power < b.power;
}
 
vector<t_info> tower;
 
bool laser()
{
    int s_x = tower[0].row;
    int s_y = tower[0].col;
    int d_x = tower[tower.size() - 1].row;
    int d_y = tower[tower.size() - 1].col;
    // 공격자와 공격 당하는 사람은 연관
    related[s_x][s_y] = true;
    related[d_x][d_y] = true;
    int split_damage = tower[0].power / 2;
 
    // 경로를 저장하는 bfs
    queue<pair<int, int>> q;
    q.push(make_pair(s_x, s_y));
    visited[s_x][s_y] = true;
 
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
 
        if (x == d_x && y == d_y)
            break;
 
        for (int k = 0; k < 4; k++)
        {
            int nx = (x + dx[k] + n) % n;
            int ny = (y + dy[k] + m) % m;
 
            if (!visited[nx][ny] && map[nx][ny] != 0)
            {
                visited[nx][ny] = true;
                q.push(make_pair(nx, ny));
                // 이렇게 경로를 저장한다
                back_x[nx][ny] = x;
                back_y[nx][ny] = y;
            }
        }
    }
 
    // 경로를 따라간다
    if (visited[d_x][d_y])
    {
        map[d_x][d_y] -= tower[0].power;
        if (map[d_x][d_y] < 0)
            map[d_x][d_y] = 0;
 
 
        int i = back_x[d_x][d_y];
        int j = back_y[d_x][d_y];
 
        while (true)
        {
            if (i == s_x && j == s_y)
                break;
            map[i][j] -= split_damage;
            if (map[i][j] < 0)
                map[i][j] = 0;
            related[i][j] = true;
 
            int next_i = back_x[i][j];
            int next_j = back_y[i][j];
 
            i = next_i;
            j = next_j;
        }
        return true;
    }
    else
        return false;
}
 
void canon()
{
    int d_x = tower[tower.size() - 1].row;
    int d_y = tower[tower.size() - 1].col;
    int split_damage = tower[0].power / 2;
 
    related[tower[0].row][tower[0].col] = true;
    related[d_x][d_y] = true;
 
    map[d_x][d_y] -= tower[0].power;
    if (map[d_x][d_y] < 0)
        map[d_x][d_y] = 0;
 
    for (int k = 0; k < 8; k++)
    {
        int nx = (d_x + canon_x[k] + n) % n;
        int ny = (d_y + canon_y[k] + m) % m;
 
        // 공격자는 영향을 받지 않음
        if (nx == tower[0].row && ny == tower[0].col)
            continue;
        if (map[nx][ny] > 0)
        {
            map[nx][ny] -= split_damage;
            related[nx][ny] = true;
            if (map[nx][ny] < 0)
                map[nx][ny] = 0;
        }
    }
}
 
void duhagi()
{
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (map[i][j] != 0 && related[i][j] == false)
                map[i][j] += 1;
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> map[i][j];
            if (map[i][j] != 0)
                tower.push_back({ i,j,0,map[i][j] });
        }
    }
    memset(rec, 0, sizeof(rec));
    for (int t = 1; t <= k; t++)
    {
        tower.clear();
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (map[i][j] > 0)
                {
                    tower.push_back({ i,j,rec[i][j], map[i][j] });
                }
            }
        }
 
        if (tower.size() <= 1)
            break;
 
        memset(visited, false, sizeof(visited));
        memset(related, false, sizeof(related));
 
        sort(tower.begin(), tower.end());
        tower[0].power += n + m;
        map[tower[0].row][tower[0].col] = tower[0].power;
        // 공격을 한다면 rec에 t를 저장
        rec[tower[0].row][tower[0].col] = t;
 
        bool chk = laser();
        if (!chk)
            canon();
 
        // 공격과 관련없는 포탑들 +1
        duhagi();
    }
 
    int ans = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            ans = max(ans, map[i][j]);
 
    cout << ans;
    return 0;
}