루돌프의 반란

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

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

점점 문제가 괴랄해져 간다.

실제 문제에서는 소와 사람으로 나와서 cow를 썼다.

 

게임판에서 두 칸 (r1​,c1​), (r2​,c2​) 사이의 거리는 

(r1​−r2​)^2+(c1​−c2​)^2으로 계산

BFS가 아니다!

#include <cmath> 해서

inline int dist 함수를 정의해주자

inline int dist(int r1, int c1, int r2, int c2)
{
    return pow((r1 - r2), 2) + pow((c1 - c2), 2);
}

1. 루돌프의 움직임 & 산타 움직임

루돌프는 가장 가까운 산타를 향해 1칸 돌진

만약 가장 가까운 산타가 2명 이상이라면, 

r 좌표가 큰 산타를 향해 돌진합니다. 

r이 동일한 경우, c 좌표가 큰 산타를 향해 돌진

 

구조체를 선언해서

구조체 연산자 오버로딩을 하자.

비교 연산을 쓰므로 그대로 간다!

bool operator < (const santa_info& s1, const santa_info& s2)
{
    if (s1.from_cow == s2.from_cow)
    {
        if (s1.s_row == s2.s_row)
            return s1.s_col < s2.s_col;
        return s1.s_row < s2.s_row;
    }
    return s1.from_cow > s2.from_cow;
}

2. crush 함수

산타는 루돌프와의 충돌 후 기절을 하게 됩니다.

현재가 k번째 턴이었다면, (k+1)번째 턴까지 기절하게 되어 

(k+2)번째 턴부터 다시 정상상태가 됩니다.

 

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

어른 상어

어른 상어에서 썼던 시간 저장 방법을 그대로 쓴다.

santas[santa_idx].stun_time = t + 1;

 

소가 박치기 한 경우와 산타가 박치기 한 경우를

하나의 함수로 처리해버리자. -> flag를 쓰면 되겠다.

 

날라간 다음 케이스 분류!

1. 맵 밖으로 나간 경우 

santas[santa_idx].live = false;

 

2. 맵 안에 있는 경우

a) 산타가 존재하는 경우 (map 값이 0이 아님)

rensai 함수 호출

b) 산타가 없는 경우 (map 값이 0)

그냥 이동 시키면 끝

 

3. rensai 함수

그 위치에 산타가 있다면 연쇄 되어 방향에 맞게 날라간다.

 

void rensai(int r, int c, int santa_num, int x_dir, int y_dir)

 

<소스 코드>

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
int n, m, p, c, d;
 
// 상 우 하 좌
int s_dx[] = { -1,0,1,0 };
int s_dy[] = { 0,1,0,-1 };
 
int cow_dx[] = { -1,-1,-1,0,0,1,1,1 };
int cow_dy[] = { -1,0,1,-1,1,-1,0,1 };
 
int change_dir(int dir)
{
    if (dir == 0)
        return 7;
    else if (dir == 1)
        return 6;
    else if (dir == 2)
        return 5;
    else if (dir == 3)
        return 4;
    else if (dir == 4)
        return 3;
    else if (dir == 5)
        return 2;
    else if (dir == 6)
        return 1;
    else if (dir == 7)
        return 0;
}
 
struct cow_info {
    int c_row;
    int c_col;
 
    cow_info()
    {
        c_row = -1;
        c_col = -1;
    }
};
 
cow_info cow;
 
int total_score = 0;
 
struct santa_info {
    int s_row;
    int s_col;
    int from_cow;
    int stun_time;
    bool live;
};
 
santa_info santas[31];
 
int scores[31];
int map[55][55];
 
inline int dist(int r1, int c1, int r2, int c2)
{
    return pow((r1 - r2), 2) + pow((c1 - c2), 2);
}
 
bool operator < (const santa_info& s1, const santa_info& s2)
{
    if (s1.from_cow == s2.from_cow)
    {
        if (s1.s_row == s2.s_row)
            return s1.s_col < s2.s_col;
        return s1.s_row < s2.s_row;
    }
    return s1.from_cow > s2.from_cow;
}
 
// 소가 박을 산타 정하기
int determine_santa()
{
    // 기준 산타 정하기
    santa_info near_santa;
    int santa_idx = -1;
    for (int i = 1; i <= p; i++)
    {
        if (santas[i].live == false)
            continue;
        santas[i].from_cow = dist(santas[i].s_row, santas[i].s_col, cow.c_row, cow.c_col);
        santa_idx = i;
        near_santa = santas[i];
        // 하나 정했으면 바로 break
        break;
    }
 
    for (int i = santa_idx + 1; i <= p; i++)
    {
        if (santas[i].live == false)
            continue;
        santas[i].from_cow = dist(santas[i].s_row, santas[i].s_col, cow.c_row, cow.c_col);
        // 구조체 비교
        if (near_santa < santas[i])
        {
            santa_idx = i;
            near_santa = santas[i];
        }
    }
 
    return santa_idx;
}
 
void rensai(int r, int c, int santa_num, int x_dir, int y_dir)
{
    // 범위 안에 있어야하고
    if (r >= 1 && r <= n && c >= 1 && c <= n)
    {
        // 산타가 존재
        if (map[r][c] != 0)
        {
            int nr = r + x_dir;
            int nc = c + y_dir;
            rensai(nr, nc, map[r][c], x_dir, y_dir);
            // 재귀를 탈출하면서 그 위치에 저장
            map[r][c] = santa_num;
            santas[santa_num].s_row = r;
            santas[santa_num].s_col = c;
            return;
        }
        // 산타가 없음
        else
        {
            map[r][c] = santa_num;
            santas[santa_num].s_row = r;
            santas[santa_num].s_col = c;
            return;
        }
    }
    // 범위 밖으로 감
    else
    {
        santas[santa_num].live = false;
        return;
    }
}
 
// true면 소 박치기
// false면 산타 박치기
void crush(int santa_idx, int dir, int t, bool flag)
{
    santas[santa_idx].stun_time = t + 1;
 
    // 소 박치기
    if (flag)
    {
        map[santas[santa_idx].s_row][santas[santa_idx].s_col] = 0;
        santas[santa_idx].s_row += (cow_dx[dir] * c);
        santas[santa_idx].s_col += (cow_dy[dir] * c);
        scores[santa_idx] += c;
    }
    // 산타 박치기
    else
    {
        // 반대로 가야함
        dir += 2;
        if (dir > 3)
        {
            dir %= 4;
        }
 
        map[santas[santa_idx].s_row][santas[santa_idx].s_col] = 0;
        santas[santa_idx].s_row += (s_dx[dir] * d);
        santas[santa_idx].s_col += (s_dy[dir] * d);
        scores[santa_idx] += d;
    }
 
    // 맵 밖으로 나간 경우
    if (santas[santa_idx].s_row < 1 || santas[santa_idx].s_row > n || santas[santa_idx].s_col < 1 || santas[santa_idx].s_col > n)
    {
        santas[santa_idx].live = false;
    }
 
    // 맵 안에 있음
    if (santas[santa_idx].s_row >= 1 && santas[santa_idx].s_row <= n && santas[santa_idx].s_col >= 1 && santas[santa_idx].s_col <= n)
    {
        // 산타가 존재하는 경우
        if (map[santas[santa_idx].s_row][santas[santa_idx].s_col] > 0)
        {
            if (flag)
                rensai(santas[santa_idx].s_row, santas[santa_idx].s_col, santa_idx, cow_dx[dir], cow_dy[dir]);
            else
                rensai(santas[santa_idx].s_row, santas[santa_idx].s_col, santa_idx, s_dx[dir], s_dy[dir]);
        }
        // 그냥 착지
        if (map[santas[santa_idx].s_row][santas[santa_idx].s_col] == 0)
        {
            map[santas[santa_idx].s_row][santas[santa_idx].s_col] = santa_idx;
        }
    }
}
 
 
void cow_move(int t)
{
    int m_x, m_y, c_dir;
    // 박을 산타 정하기
    int idx = determine_santa();
    
    // 산타가 다 뒤진 상태
    if (idx == -1)
        return;
    
    // 소와의 거리
    int tmp = santas[idx].from_cow;
 
    // 거리가 가까워지는 방향으로 박아야한다
    for (int k = 0; k < 8; k++)
    {
        int nx = cow.c_row + cow_dx[k];
        int ny = cow.c_col + cow_dy[k];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= n)
        {
            if (dist(nx, ny, santas[idx].s_row, santas[idx].s_col) < tmp)
            {
                tmp = dist(nx, ny, santas[idx].s_row, santas[idx].s_col);
                m_x = nx;
                m_y = ny;
                c_dir = k;
            }
        }
    }
 
    // 소 위치 이동
    cow.c_row = m_x;
    cow.c_col = m_y;
 
    // 산타가 있다면 crush 시작
    if (map[cow.c_row][cow.c_col] > 0)
    {
        crush(map[cow.c_row][cow.c_col], c_dir, t, true);
    }
}
 
void santa_move(int t)
{
    for (int i = 1; i <= p; i++)
    {
        if (santas[i].live == false || (santas[i].stun_time >= t))
            continue;
 
        // 이동 전 소와의 거리, gijun_x, gijun_y
        int tmp = dist(santas[i].s_row, santas[i].s_col, cow.c_row, cow.c_col);
        int gijun_x = santas[i].s_row;
        int gijun_y = santas[i].s_col;
        int s_dir;
 
        for (int k = 0; k < 4; k++)
        {
            int nx = gijun_x + s_dx[k];
            int ny = gijun_y + s_dy[k];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= n)
            {
                if (dist(nx, ny, cow.c_row, cow.c_col) < tmp)
                {
                    // 산타있으면 못감
                    if (map[nx][ny] > 0)
                        continue;
                    // tmp 갱신
                    tmp = dist(nx, ny, cow.c_row, cow.c_col);
                    santas[i].s_row = nx;
                    santas[i].s_col = ny;
                    s_dir = k;
                }
            }
        }
 
        map[gijun_x][gijun_y] = 0;
        map[santas[i].s_row][santas[i].s_col] = i;
 
        // 좌표가 완전히 일치한다면
        // 산타 crush 시작
        if ((santas[i].s_row == cow.c_row) && (santas[i].s_col == cow.c_col))
        {
            crush(i, s_dir, t, false);
            continue;
        }
    }
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    memset(scores, 0, sizeof(scores));
    cin >> n >> m >> p >> c >> d;
 
    cin >> cow.c_row >> cow.c_col;
 
    for (int i = 0; i < p; i++)
    {
        int n, r, c;
        cin >> n >> r >> c;
        santas[n] = { r,c,0,0, true };
        // 그냥 map에 산타 바로 그린다
        map[r][c] = n;
    }
 
    for (int i = 1; i <= m; i++)
    {
        cow_move(i);
        santa_move(i);
 
        for (int i = 1; i <= p; i++)
        {
            if (santas[i].live)
            {
                scores[i] += 1;
            }
        }
    }
 
    for (int i = 1; i <= p; i++)
        cout << scores[i] << ' ';
 
    return 0;
}