[백준] 마법사 상어와 파이어볼

유승선 ·2022년 7월 18일
0

백준

목록 보기
35/64

주말동안 잠깐 쉬는 시간도 가지고 재충전을 끝내고 돌아와서 또 한번 백준 문제를 풀어보았다. 그리고 처음에는 쉬울 줄 알았던 이 문제에서 굉장히 많은 어지러움을 느꼈는데 너무 자잘한 실수 몇개 때문에 문제를 전부 푸는데 말도 안되는 시간이 걸렸어가지고 너무 많은 현타와 함께 자아성찰의 시간을 가지게 되었다.

이번에도 문제는 마법사 상어와 관련된 문제이고 N * N 메트릭스 안에서 M 개의 파이어볼이 들어있는 이동 마법을 K 만큼 해서 남은 파이어볼의 무게를 합해서 출력하면 되는 문제였다. 그리고 파이어볼 같은 경우 정보란에 위치 r, c 무게인 m 그리고 속도와 방향을 나타내는 s 와 d 로 구성되어있다. 뱡향 같은 경우는 8가지 방향으로 이동가능하며 가지고 있는 속도 만큼 칸을 지나갈수 있다. 이 문제에 핵심은 정말 말 그대로 문제를 따라가면은 되는 문제였지만 몇가지 고려 해야 되는부분들이 많았다.

  1. 파이어볼은 중첩이 될 수 있다는점
  2. 파이어볼에 이동 범위가 메트릭스 밖으로 이어질 수 있고 끝과 끝 지점을 연결 시켜줘야 한다는 점
  3. 파이어볼이 중첩될 경우 4가지 작은 불로 나뉘는데 알맞은 계산법과 알맞은 방향을 줘야한다는 점

솔직히 위에 세가지 구현이 좀 까다로운 부분이 있어서 이 문제가 골드 4에 속해있지 않을까 싶긴하다. 그리고 나는 여기서 굉장히 많은 뻘짓을 했었다. 내가 했던 뻘짓을 좀 나열해 보겠다.

  1. 문제를 자세히 읽지 않았어서 r,c,m,s,d 위치 -> 무게 -> 속도 -> 방향 순인데, r,c,m,d,s 위치 -> 무게 -> 방향 -> 속도 순으로 문제를 이해하고 있었어서 첫번째 예시 조차 저게 왜 저 답이지 하고 혼자 애태우면서 시간을 낭비했다. 당연히 방향과 속도는 같지 않기때문에 너무나도 큰 뻘짓 이었다.

  2. 질량이 0 인 파이어볼은 소멸되어야 했는데 해당 시물레이션에 맞는 계산법 후에 질량 0인 파이어볼을 제거해줘야 되는것을 계산을 적용하기 전 파이어볼 질량으로 코드를 써서 또 한번 뻘하게 시간을 날렸다.

  3. 마지막으로 제일 큰 뻘짓이었는데 아무리 코드를 맞게 썼는데도 틀려서 뭐지 하고 계속 cout 으로 버그를 찾았는데 내가 설정한 dir 벡터에서 방향 한 곳을 쌩뚱맞은데로 지정을 했었다. (1,1), (1,1) 방향을 두번 중첩해서 썼고, 당연히 이런 말도 안되는 방향으로 이동을 해서 답이 맞을수가 없었다.

오랜 시간 끝에 코드를 고쳤고 K 만큼의 이동을 시작으로 move 와 divide 를 한번에 해주었다. 결국에 남는 파이어볼만 계산 하는 거였기 때문에 잘 써줬어야했다.

그래도 위에 뻘짓을 하고 나서도 잘했다고 생각한 부분 중 하나는, 파이어볼이 중첩이 된다는 점을 생각해서 처음으로 Matrix 자체를 파이어볼 스트럭쳐 벡터로 만들어주었다. 그렇기 때문에 해당 지점마다 중첩으로 파이어볼을 쌓을수 있었고 아이디어 구상은 잘했다고 생각한다.

문제에 dir 벡터...꼭 잘 확인하자..

또 한번 중요했던 부분은, 속도를 N 으로 % 해줬어야했다. 안그랬으면 오버플로우가 났을것이다. for 룹 하나하나 s 만큼 올려주기에는 아마 시간 초과가 났을거라고 생각한다. 그렇기 때문에 저렇게 한번에 계산을 해주고 더해주는게 맞는 선택이었다.

시나리오에 맞게 써줬지만 역시나 좀 더 발전시킬 가능성이 있는 코드라고 생각한다.

#include <iostream> 
#include <bits/stdc++.h> 
#define endl "\n"
#define MAX 55
using namespace std;

struct Fireball{
    int x, y, mass, speed, direction; 
};
int N, M, K; //N = matrix size, fireball number, operation number 
vector<pair<int,int>> dir = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}}; 
vector<Fireball> matrix[51][51]; 
vector<Fireball> fire_lst; 
int T_dir[] = {0,2,4,6};
int F_dir[] = {1,3,5,7}; 


void Input(){
    cin >> N >> M >> K; 
    for(int i = 0; i < M; i++){
        int x, y, m, s, d; 
        cin >> x >> y >> m >> s >> d; 
        Fireball fire; 
        fire.x = x, fire.y = y, fire.mass = m, fire.speed = s, fire.direction = d;
        matrix[x][y].push_back(fire); 
        fire_lst.push_back(fire); 
    }
    //파이어볼에 해당 위치에 벡터 형식으로 넣어주었고 
    //파이어볼만 담은 리스트는 따로 보관해준다 
}

void move_fire(){
    //파이어볼을 담은 리스트를 나중에도 쓸거이기 때문에 초반 벡터는 리셋해준다 
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            matrix[i][j].clear(); 
        }
    }

    //파이어볼 리스트를 읽어주며 이동해준다
    for(Fireball& fire : fire_lst){
        int x = fire.x, y = fire.y, m = fire.mass, s = fire.speed, d = fire.direction;

        int nX = x + (dir[d].first * (s % N)); //속도로 인한 오버플로우 막기
        int nY = y + (dir[d].second * (s % N)); 
        //첫번쨰 행과 마지막 행, 그리고 첫번째 열과 마지막 열은 연결되어있다 
        if(nX >= N) nX -= (N); 
        if(nX < 0) nX += (N);
        if(nY >= N) nY -= (N);
        if(nY < 0) nY += (N); 
        fire.x = nX, fire.y = nY; 
        matrix[nX][nY].push_back(fire); 

    }
}

void divide_fire(){
    //Matrix에 남아있는 Fire을 기준으로 불을 나눌것이다 
    fire_lst.clear();
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(matrix[i][j].size() == 1){ //만약 겹치는곳이 아무것도 없다면 
                fire_lst.push_back(matrix[i][j][0]); 
            }
            if(matrix[i][j].size() > 1){ //2개 이상의 파이어볼이 겹칠때
                int nM = 0, nS = 0, cnt = matrix[i][j].size();

                bool even = true, odd = true; 
                for(int k = 0; k < matrix[i][j].size(); k++){
                    nM += matrix[i][j][k].mass; 
                    nS += matrix[i][j][k].speed;
                    if(matrix[i][j][k].direction % 2 == 0) odd = false;
                    else even = false; 
                }

                int final_mass = nM / 5;
                int final_speed = nS / cnt; 
                if(final_mass != 0){
                    if(even == true || odd == true){
                        for(int k = 0; k < 4; k++){
                            fire_lst.push_back({i,j,final_mass,final_speed,T_dir[k]}); 
                        }
                    }
                    else{
                        for(int k = 0; k < 4; k++){
                            fire_lst.push_back({i,j,final_mass,final_speed,F_dir[k]}); 
                        }
                    }
                }

            }
        }
    }
}

void Solution(){
    //K만큼의 명령이 필요하다 
    for(int i = 0; i < K; i++){
        move_fire();
        divide_fire(); 
    }
    int answer = 0; 
    for(Fireball& f : fire_lst){
        answer += f.mass; 
    }

    cout << answer; 
}


void Solve(){
    Input();
    Solution(); 
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "r", stdin);
    Solve();
    return 0;

}

문제가 너무 막히는 감도 있었어서 얍문님의 블로그도 참고 했고 그래도 재밌는 문제였다. 다만 시물레이션 문제는 정말 중간에 어떤 포인트를 놓치면 답도 없게 미궁으로 빠지기 때문에 항상 내가 뭘 하고 있는지 아는게 중요한거같다.

배운점:
1. 문제를 잘 읽고, 변수를 만들때도 문제와 맞는지 확인해보자
2. 침착하게 풀자

profile
성장하는 사람

0개의 댓글