[백준_20056(마법사 상어와 파이어볼)

https://www.acmicpc.net/problem/20056

20056번: 마법사 상어와 파이어볼

문제 설명

1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.
이는 1을 넘어가면 =>N ,N을 넘어가면 1이 된다는 의미다.(이 부분을 이해하지 못해 1시간 이상 낭비했다...)

문제 풀이

• 파이어볼 이동시간 복잡도 O(NNs10004), 나누는 시간 복잡도O(NN4) 이기때문에 시뮬레이션 구현이 가능하다.
• 한 좌표에 대해 넣을 수 있는 파이어 볼이 4개 이니 vector <{m.s.d}>map [51][51] 자료 구조를 이용한다.

1. 파이어볼 이동
   1. 모든 좌표를 돌면서 해당 좌표에 파이어볼이 있으면 s만큼 이동
   • 방향대로 이동 시 ,범위를 안 넘으면 계속 진행
   • 만일 범위를 넣으면 각 행,열 좌표에서 N에서=>1,1==>N으로 이동여기서 삽질을 많이 했다. 모든 방향마다, 조건을 걸어 줬는데 그냥 N에서=>1,1==>N 검사로 통일해도 된다.
     끝지점에서만 범위 넘어가는 예외 처리만 해줘서 처음에 틀렸다.(ex. 2,3위치세 있을때 1번 방향으로 이동)
   2. s만큼 이동 후 해당 파이어볼 위치에 {m,s,d} 추가
2. 파이어볼 합치고 나누기
   1. 모든 좌표를 돌면서 해당 좌표에 파이어볼이 1이상이면
   2. ⌊(합쳐진 파이어볼 질량의 합)/5⌋,속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋,파이어볼의 방향을 체크한다.
      • 방향 체크는 odd 변수에 방향이 짝수일 때 +1 ,홀수 일때 -1로 카운팅함
      • |odd | 값이 해당 좌표 파이어볼의 갯수와 같은 지 체크)
3. 해당 좌표의 vector을 초기화 하고 4개로 나뉜 파이어볼 {m,s,d} 추가

 

#include <iostream>
#include <vector>

using namespace std;
struct Point
{

    int m, s, d;
};

int N, M, K;
vector<Point> map[51][51];

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

void move()
{
    vector<Point> temp[51][51];

    for (int i = 1; i <= N; i++)
    {

        for (int j = 1; j <= N; j++)
        {
            if (map[i][j].size())
            {
                for (int k = 0; k < map[i][j].size(); k++) //해당 좌표의 파이어 볼이 있다면,
                {
                    int s = map[i][j][k].s;
                    int cnt = s;
                    int m = map[i][j][k].m;
                    int d = map[i][j][k].d;

                    int x = i;
                    int y = j;
                    while (cnt--) //속도만큼 반복
                    {

                        int nx = x + dx[d];
                        int ny = y + dy[d];

                        if (nx >= 1 && nx <= N && ny >= 1 && ny <= N) //범위내에면 이동
                        {
                            x = nx;
                            y = ny;
                        }
                        else
                        {
                            //범위를 넘어가면 각 행렬의 N에서=>1,1==>N으로 이동
                            if (nx < 1)
                            {
                                nx = N;
                            }
                            if (ny < 1)
                            {
                                ny = N;
                            }
                            if (nx > N)
                            {
                                nx = 1;
                            }
                            if (ny > N)
                            {
                                ny = 1;
                            }

                            x = nx;
                            y = ny;
                        }
                    }
                    temp[x][y].push_back({m, s, d}); //최종 결과추가
                }
            }
        }
    }

    for (int i = 1; i <= N; i++)
    {

        //맵에 복사

        for (int j = 1; j <= N; j++)
        {
            map[i][j] = temp[i][j];
        }
    }
}

void cal()
{

    for (int i = 1; i <= N; i++)
    {

        for (int j = 1; j <= N; j++)
        {
            if (map[i][j].size() > 1)
            {
                //한개가 아닌 여러개 있을때
                int m_sum = 0;
                int s_sum = 0;
                int odd = 0;
                int map_size = map[i][j].size();

                for (int k = 0; k < map_size; k++)
                {

                    m_sum += map[i][j][k].m; //질량들의 합
                    s_sum += map[i][j][k].s; //속도의 합

                    if ((map[i][j][k].d) % 2 == 0)
                    {
                        //방향 양수인지 체크
                        odd++;
                    }
                    else
                    {
                        //혹수인지 체크
                        odd--;
                    }
                }

                m_sum /= 5;
                s_sum /= map_size;

                map[i][j].clear(); //비워줌

                if (m_sum) //질량이 소멸되지 않을 경우
                {
                    for (int k = 0; k < 7; k += 2)
                    {
                        if (odd == map_size || -odd == map_size)
                        {
                            //방향이 홀수만 나오거나,짝수만 나올경우
                            map[i][j].push_back({m_sum, s_sum, k});
                            // 방향(0,2,4,6)으로 고정
                        }
                        else
                        {
                            map[i][j].push_back({m_sum, s_sum, k + 1});
                            // 방향(1,3,5,7)으로 고정
                        }
                    }
                }
            }
        }
    }
}
int main()
{

    cin >> N >> M >> K;

    for (int i = 0; i < M; i++)
    {

        int x, y, m, s, d;
        cin >> x >> y >> m >> s >> d;
        map[x][y].push_back({m, s, d});
    }

    int ans = 0;
    while (K--)
    {

        move(); //이동
        cal();  //파이어볼로 합치고 나눔
    }

    for (int i = 1; i <= N; i++)
    {
        //최종 카운팅

        for (int j = 1; j <= N; j++)
        {
            if (map[i][j].size())
            {
                for (int k = 0; k < map[i][j].size(); k++)
                {

                    ans += map[i][j][k].m;
                }
            }
        }
    }

    cout << ans << '\n';

    return 0;
}