[C++] 백준/BOJ - 20056 : 마법사 상어와 파이어볼

문제 이해 단계

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

NxN인 격자에 M개의 파이어볼을 쏜다. 그리고 K번만큼 이동한다.

파이어볼은 5가지의 정보를 가지고 있는데,
(x좌표, y좌표, 질량, 속력, 방향)이다.

1. 자신의 방향으로 자신의 속력만큼 움직인다.
2. 이동이 끝난 후 파이어볼이 같은 칸에 있는 것이 있다면 하위에 프로세스를 실행한다.

2 - 1. 같은 칸에 있는 파이어볼을 합한다.(질량, 속력 전부)
2 - 2. 합쳐진 파이어볼은 4개로 나뉜다.
2 - 3. 각 파이어볼의 속력은 (속력의 합/개수), 질량은 (질량의 합/5)이다.
2 - 4. 방향은 합쳐진 파이어볼의 각 방향이 모두 홀수거나 짝수면 0,2,4,6 그렇지 않으면 1,3,5,7이다.
2 - 5. 질량이 0인 파이어볼은 삭제한다.

이동할 때는 2가지 단계를 걸친다. 이 과정은 계속 반복한다.
해당 과정을 K번 반복했을 때 남아있은 파이어볼의 질량의 합을 구하는 문제

 

---

문제 접근 단계

해야 하는 일들이 단계별로 나와있는 것 보니까 구현, 더 깊게는 시뮬레이션 같다.
근데 문제가 뭔가 이해하기 어렵다.

뭔가 로직적으로 기발한 아이디어가 있다기보다는
단순 구현문제인 거 같아서 진짜 구현만 하면 될 것 같다.

일단, 해당 문제에서 들어오는 정보가 5가지나 된다.

x좌표, y좌표, 질량, 속력, 방향이 5가지를 따로따로 처리하기에는
많이 귀찮을뿐더러, 헷갈릴 수 있기 때문에 이를 하나로 묶는 구조체를 썼다.

struct Info{
    int x;
    int y;
    int w;
    int speed;
    int dir;
};

이런 식으로 Info라는 구조체를 선언했다.

 

---

같은 칸에 있는 여러 개의 파이어볼

해당 문제의 특징은 2차원 맵의 각 칸에 원소(파이어볼)가 여러 개 들어갈 수 있다는 것이다.
그리고 그 원소들의 정보가 각각 따로 저장되어 있어야 하기 때문에 리스트형으로 저장해 두었다.

vector <Info> map [51][51] 이런 식으로 말이다.
이렇게 각 파이어볼의 정보들은 모두 살려두면서, 각 칸의 몇 개의 파이어볼이 들어가 있는지도 알  수 있다.

 

---

파이어볼 이동시키기

파이어볼이 이동하는 거리는 방향 x속력을 따른다.

여기서 문제가 되는 사항은 1번 열과 N번 열이 연결되어 있다는 것이다.

분명히 방향 x속력이 N이상일 수도 있고, 속력이 음수로 가면 0 이하일 수도 있다.
이걸 0~7 사이에 정확한 위치로 맞춰야 한다.

이 부분은 코드로 설명하겠다.

 

---

4개의 파이어볼로 나누기

같은 칸에 있는 여러 개의 파이어볼은,
이제 4개의 파이어볼로 나눠야 한다.

파이어볼을 합치기 전에 정보들을 모아
나뉘었을 때의 정보를 미리 빼두면 이를 구하기가 쉬워진다.

이 부분은 로직적으로는 크게 문제가 안되기 때문에
코드 구현 단계에서 코드로 보는 것이 훨씬 편하다.

이렇게 우리가 집중해서 구현해야 할 부분들에 대해 살펴보았고, 이를 유의하여서 구현해 보자.

 

---

문제 구현 단계

truct Info{
    int x;
    int y;
    int w;
    int speed;
    int dir;
};

// 위치대로 움직임
int dx[] = {-1,-1,0,1,1,1,0,-1};
int dy[] = {0,1,1,1,0,-1,-1,-1};

vector<Info> map[55][55];
vector<Info> fire;
int N,M;

// 파이어볼을 움직이는 함수
void moveFire(){
    // 새로운 파이어볼을 받기위해 맵 자체를 초기화
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= N; j++) map[i][j].clear();

    // 파이어볼 개수만큼
    for(int i = 0; i < fire.size(); i++){
        // 파이어볼 정보를 받음-------
        int x = fire[i].x;
        int y = fire[i].y;
        int w = fire[i].w;
        int dir = fire[i].dir;
        int speed = fire[i].speed;
        //-----------------------
        
        // 이동 거리 (nx,ny)
        int nx = x+dx[dir]*speed;
        int ny = y+dy[dir]*speed;

        // nx,ny가 0보다 작다면 N씩 더해서 위치를 맞춤
        while(nx < 1) nx += N;
        while(ny < 1) ny += N;
        // N보다 크면 N씩 빼서 크기를 맞춤
        while(nx > N) nx -= N;
        while(ny > N) ny -= N;
        // 그 위치에 넣음
        map[nx][ny].push_back({nx,ny,w,speed,dir});
    }
}

파이어볼을 움직이는 moveFire() 함수이다.

우선적으로 맵 자체에 파이어볼을 모두 없애야 한다.

그 이유는 새로운 파이어볼을 생성해야 하는데,
이는 vector에 push_back으로 넣어줘, 자칫하면 있던 공간에 쌓여 중첩될 수가 있기 때문이다.

맵을 초기화한 다음, 파이어볼의 개수만큼 움직이는 것을 시작한다.

파이어볼의 정보를 모두 받은 다음, 방향에 따라 이동할 거리를 계산한다. 
그 이동할 거리를 while문을 사용하여 0 ~ N사이의 거리로 맞춰준다.

while문을 사용하는 이유는 몇 번의 N을 더해줘야 그 사이로 들어오는지 모르기 때문이다.
그 이후에 값을 넣어준다.

// 해당 파이어볼들이 전부 짝수인지, 홀수인지 체크
bool isDir(int x, int y){
    bool even = true, odd = true;
    for(int i = 0; i < map[x][y].size(); i++){
        if(map[x][y][i].dir % 2 == 0){
            odd = false;
            break;
        }
    }

    for(int i = 0; i < map[x][y].size(); i++){
        if(map[x][y][i].dir % 2 != 0){
            even = false;
            break;
        }
    }
    if(even || odd) return true;
    return false;

}
void splitFire(){
    vector<Info> newFire; // 4개로 나누어진 새로운 파이어볼
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            int weight = 0;
            int speed = 0;
            int dir = 0;
            bool checkDir = isDir(i,j);
            // 비어있거나 0이면 패스
            if(map[i][j].empty() || map[i][j].size() == 0) continue;
            // 1이면 그냥 값을 담음
            else if(map[i][j].size() == 1) newFire.push_back(map[i][j][0]);
            // 2 이상일 경우
            else
            {
                for(int k = 0; k < map[i][j].size(); k++){
                    speed += map[i][j][k].speed; // 속력의 합
                    weight += map[i][j][k].w; // 중량의 합
                }
                // 계산
                speed = (speed / map[i][j].size());
                weight = (weight / 5);
                
                if(weight == 0) continue;
                for(int k = 0; k < 8; k++){
                    if(checkDir && k % 2 == 0) {
                        newFire.push_back({i,j,weight,speed,k}); // 0,2,4,6 방향인 파이어볼 생성
                    }
                    else if(!checkDir && k%2 == 1) {
                        newFire.push_back({i,j,weight,speed,k}); // 1,3,5,7 방향인 파이어볼 생성
                    }
                }
            }
        }
    }
    fire = newFire; // 파이어볼을 갱신
}

해당 칸에 있는 파이어볼의 방향들이 모두 짝수 혹은 홀수인지 체크하는 isDir과
파이어볼을 4개로 분리하는 splitFire함수이다.

 isDir은 모두 짝수 혹은 홀수면 true, 아니면 false를 반환한다.

 

SplitFire은 총 3가지 경우로 나뉘는데,
해당 칸이 0개면 그냥 패스, 1개면 그냥 그 값을 새로운 파이어볼로 한다.

2개 이상일 때만 4개로 나누는 작업을 하는데,
이때 모든 속력과 질량을 더하고 계산을 한다.

그리고 앞에서 계산해 둔 Dir을 이용하여 4가지 방향인 새로운 파이어볼을 만든 후,
이 새로운 파이어볼을 모아 둔 변수 newFire을 전역변수 fire에 전달하여 끝낸다.

여기까지가 핵심 로직의 설명의 끝이다.
아래는 전체 코드를 올리고 마치겠다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Info{
    int x;
    int y;
    int w;
    int speed;
    int dir;
};

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

vector<Info> map[55][55];
vector<Info> fire;
int N,M;


// 파이어볼을 움직이는 함수
void moveFire(){
    // 새로운 파이어볼을 받기위해 맵 자체를 초기화
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= N; j++) map[i][j].clear();

    // 파이어볼 개수만큼
    for(int i = 0; i < fire.size(); i++){
        // 파이어볼 정보를 받음-------
        int x = fire[i].x;
        int y = fire[i].y;
        int w = fire[i].w;
        int dir = fire[i].dir;
        int speed = fire[i].speed;
        //-----------------------
        
        // 이동 거리 (nx,ny)
        int nx = x+dx[dir]*speed;
        int ny = y+dy[dir]*speed;

        // nx,ny가 0보다 작다면 N씩 더해서 위치를 맞춤
        while(nx < 1) nx += N;
        while(ny < 1) ny += N;
        // N보다 크면 N씩 빼서 크기를 맞춤
        while(nx > N) nx -= N;
        while(ny > N) ny -= N;
        // 그 위치에 넣음
        map[nx][ny].push_back({nx,ny,w,speed,dir});
    }
}
// 해당 파이어볼들이 전부 짝수인지, 홀수인지 체크
bool isDir(int x, int y){
    bool even = true, odd = true;
    for(int i = 0; i < map[x][y].size(); i++){
        if(map[x][y][i].dir % 2 == 0){
            odd = false;
            break;
        }
    }

    for(int i = 0; i < map[x][y].size(); i++){
        if(map[x][y][i].dir % 2 != 0){
            even = false;
            break;
        }
    }
    if(even || odd) return true;
    return false;

}
void splitFire(){
    vector<Info> newFire; // 4개로 나누어진 새로운 파이어볼
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            int weight = 0;
            int speed = 0;
            int dir = 0;
            bool checkDir = isDir(i,j);
            // 비어있거나 0이면 패스
            if(map[i][j].empty() || map[i][j].size() == 0) continue;
            // 1이면 그냥 값을 담음
            else if(map[i][j].size() == 1) newFire.push_back(map[i][j][0]);
            // 2 이상일 경우
            else
            {
                for(int k = 0; k < map[i][j].size(); k++){
                    speed += map[i][j][k].speed; // 속력의 합
                    weight += map[i][j][k].w; // 중량의 합
                }
                // 계산
                speed = (speed / map[i][j].size());
                weight = (weight / 5);
                
                if(weight == 0) continue;
                for(int k = 0; k < 8; k++){
                    if(checkDir && k % 2 == 0) {
                        newFire.push_back({i,j,weight,speed,k}); // 0,2,4,6 방향인 파이어볼 생성
                    }
                    else if(!checkDir && k%2 == 1) {
                        newFire.push_back({i,j,weight,speed,k}); // 1,3,5,7 방향인 파이어볼 생성
                    }
                }
            }
        }
    }
    fire = newFire; // 파이어볼을 갱신
}
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

    int K;
    cin >> N >> M >> K;
    for(int i = 0; i < M; i++){
        int v1,v2,v3,v4,v5;
        cin >> v1 >> v2 >> v3 >> v4 >> v5;
        fire.push_back({v1,v2,v3,v4,v5});
    }

    while(K--){
        moveFire();
        splitFire();
    }
    int ans = 0;
    for(int i = 0; i < fire.size(); i++) ans+= fire[i].w;
    cout << ans;
}

 

---

시행착오

엄청나게 오래 걸렸다. 그리고 풀지 못했다.

아이디어 자체는 쉬웠었는데,
0 ~ N 사이로 정확하게 들어오게 하는데 실패했다.

처음에는 모듈러 연산을 사용해서 했는데 실패,
그걸로 어떻게든 해보려다가 너무 시간을 많이 써버렸다.

답지를 보는데도, 오래 걸렸다.
저 방식은 이해가지만 왜 내가 했던 방식이 되지 않는지 이해가 가지 않는다.

중간중간 out of bound가 떴기도 했고 화도 많이 나고, 그냥 자신감이 많이 없어졌다.