백준 20056번 마법사 상어와 파이어볼 [C++]/삼성 SW역량 테스트 기출 문제

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

 

 

#개요

말 그대로 따라가면 정답을 얻을 수 있는 구현문제지만

풀기 전에 설계를 정확하게 한 후에 최대한 실수를 적게 하도록 하자.

특히 3차원 벡터를 사용하기때문에 실수하기 쉽기 때문에 체감난이도가 조금 더 높게 느껴 질 수 있다.

 

#전체 코드

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

#define MAX 52
using namespace std;

struct fireBall {
    int y;
    int x;
    int mass;
    int speed;
    int dir;
};

int N, M, K;
vector<fireBall> mapVec[MAX][MAX];

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

// 경계 조정 함수
int isBoundary(int x) {
    if (x > N) {
        x = x % N;
    }
    if (x < 1) {
        x = N + (x % N);
    }

    return x;
}

void moveFireBall() {
    vector<fireBall> temp[MAX][MAX];

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (mapVec[i][j].size() == 0) {
                continue;
            }
            else {
                for (int k = 0; k < mapVec[i][j].size(); k++) {
                    int mass = mapVec[i][j][k].mass;
                    int speed = mapVec[i][j][k].speed;
                    int dir = mapVec[i][j][k].dir;
                    int ny = isBoundary(dy[dir] * speed + mapVec[i][j][k].y);
                    int nx = isBoundary(dx[dir] * speed + mapVec[i][j][k].x);

                    temp[ny][nx].push_back({ ny,nx,mass,speed,dir });
                }
                mapVec[i][j].clear();
            }
        }
    }

    // 격자 상태 업데이트
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            mapVec[i][j] = temp[i][j];
        }
    }
}

void sumFireBall() {
    vector<fireBall> temp[MAX][MAX];

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (mapVec[i][j].size() == 0) {
                continue;
            }
            else if (mapVec[i][j].size() == 1) {
                temp[i][j] = mapVec[i][j];
            }
            else {
                int sumMass = 0;
                int sumSpeed = 0;
                bool sameDir = true; 
                for (int t = 0; t < mapVec[i][j].size(); t++) {
                    sumMass += mapVec[i][j][t].mass;
                    sumSpeed += mapVec[i][j][t].speed;
                    
                    if (t > 0 && mapVec[i][j][t].dir % 2 != mapVec[i][j][t - 1].dir % 2) {
                        sameDir = false;
                    }
                }

                sumMass /= 5;
                sumSpeed /= mapVec[i][j].size();

                if (sumMass == 0) {
                    continue; 
                }

                for (int d = 0; d < 4; d++) {
                    if (sameDir) {
                        temp[i][j].push_back({ i, j, sumMass, sumSpeed, d * 2 });
                    }
                    else {
                        temp[i][j].push_back({ i, j, sumMass, sumSpeed, d * 2 + 1 });
                    }
                }
            }
        }
    }

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

int main() {
    cin >> N >> M >> K;

    for (int i = 0; i < M; i++) {
        int y, x, m, s, d;
        cin >> y >> x >> m >> s >> d;
        mapVec[x][y].push_back({ y,x,m,s,d });
    }

    for (int i = 0; i < K; i++) {
        moveFireBall();
        sumFireBall();
    }

    int result = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 0; k < mapVec[i][j].size(); k++) {
                result += mapVec[i][j][k].mass;
            }
        }
    }

    cout << result << '\n';

    return 0;
}

 

 

#설계

int main() {
    cin >> N >> M >> K;

    for (int i = 0; i < M; i++) {
        int y, x, m, s, d;
        cin >> y >> x >> m >> s >> d;
        mapVec[x][y].push_back({ y,x,m,s,d });
    }

    for (int i = 0; i < K; i++) {
        moveFireBall();
        sumFireBall();
    }

    int result = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 0; k < mapVec[i][j].size(); k++) {
                result += mapVec[i][j][k].mass;
            }
        }
    }

    cout << result << '\n';

    return 0;
}

 

우선 시작할때 생각 할 수 있는것은

1. 파이어볼을 이동시키기

2. 파이어볼을 나누기

두가지 큰 로직으로 나눌 수 있기 때문에

k번 반복하는 

moveFireBall();

sumFireBall();

두개를 구현한다고 생각한다.

 

#define MAX 52
using namespace std;

struct fireBall {
    int y;
    int x;
    int mass;
    int speed;
    int dir;
};

int N, M, K;
vector<fireBall> mapVec[MAX][MAX];

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

// 경계 조정 함수
int isBoundary(int x) {
    if (x > N) {
        x = x % N;
    }
    if (x < 1) {
        x = N + (x % N);
    }

    return x;
}

 

이후에 파이어볼의 정보를 담을 파이어볼의 구조체와

각 맵의 N을 넘어가거나 0이하가 되었을때 양 옆을 이어주기 위한

isBoundary() 함수를 작성한다.

isBoundary 함수는 단순히 N넘어갔을때 더하기 연산을 구현해도 되지만

모듈러 연산으로 구현했을 때 좀 더 깔끔 한 것 같다.

 

#이동 함수 구현

 

void moveFireBall() {
    vector<fireBall> temp[MAX][MAX];

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (mapVec[i][j].size() == 0) {
                continue;
            }
            else {
                for (int k = 0; k < mapVec[i][j].size(); k++) {
                    int mass = mapVec[i][j][k].mass;
                    int speed = mapVec[i][j][k].speed;
                    int dir = mapVec[i][j][k].dir;
                    int ny = isBoundary(dy[dir] * speed + mapVec[i][j][k].y);
                    int nx = isBoundary(dx[dir] * speed + mapVec[i][j][k].x);

                    temp[ny][nx].push_back({ ny,nx,mass,speed,dir });
                }

            }
        }
    }

    // 격자 상태 업데이트
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            mapVec[i][j] = temp[i][j];
        }
    }
}

 

 

우선 이동한 파이어볼들의 정보를 담을 

vector<fireBall> temp[MAX][MAX];

임시 벡터를 선언해주고

for (int k = 0; k < mapVec[i][j].size(); k++) {
                    int mass = mapVec[i][j][k].mass;
                    int speed = mapVec[i][j][k].speed;
                    int dir = mapVec[i][j][k].dir;
                    int ny = isBoundary(dy[dir] * speed + mapVec[i][j][k].y);
                    int nx = isBoundary(dx[dir] * speed + mapVec[i][j][k].x);

                    temp[ny][nx].push_back({ ny,nx,mass,speed,dir });
                }

만약 파이어볼이 들어있다면 

int ny = isBoundary(dy[dir] * speed + mapVec[i][j][k].y);
int nx = isBoundary(dx[dir] * speed + mapVec[i][j][k].x);

경계를 조사하며 파이어볼의 위치와 속도에 따라 갱신한 새 파이어볼을 입력해준다.

 

    // 격자 상태 업데이트
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            mapVec[i][j] = temp[i][j];
        }
    }

그리고 이동한 파이어볼의 정보가 들어있는 temp 벡터는 mapVec에 복사해주도록 한다.

 

#나누기 함수 구현

 

void sumFireBall() {
    vector<fireBall> temp[MAX][MAX];

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (mapVec[i][j].size() == 0) {
                continue;
            }
            else if (mapVec[i][j].size() == 1) {
                temp[i][j] = mapVec[i][j];
            }
            else {
                int sumMass = 0;
                int sumSpeed = 0;
                bool sameDir = true; 
                for (int t = 0; t < mapVec[i][j].size(); t++) {
                    sumMass += mapVec[i][j][t].mass;
                    sumSpeed += mapVec[i][j][t].speed;
                    
                    if (t > 0 && mapVec[i][j][t].dir % 2 != mapVec[i][j][t - 1].dir % 2) {
                        sameDir = false;
                    }
                }

                sumMass /= 5;
                sumSpeed /= mapVec[i][j].size();

                if (sumMass == 0) {
                    continue; 
                }

                for (int d = 0; d < 4; d++) {
                    if (sameDir) {
                        temp[i][j].push_back({ i, j, sumMass, sumSpeed, d * 2 });
                    }
                    else {
                        temp[i][j].push_back({ i, j, sumMass, sumSpeed, d * 2 + 1 });
                    }
                }
            }
        }
    }

 

전체적으로 벡터를 탐색하는 로직은 이전의 이동 함수와 크게 다를 건 없다.

벡터의 총 질량과 속도를 총합하고

  if (t > 0 && mapVec[i][j][t].dir % 2 != mapVec[i][j][t - 1].dir % 2) {
                        sameDir = false;
                    }

전부 짝수,홀수인지 아닌지를 판별해주는 flag 변수를 사용한다

for (int d = 0; d < 4; d++) {
                    if (sameDir) {
                        temp[i][j].push_back({ i, j, sumMass, sumSpeed, d * 2 });
                    }
                    else {
                        temp[i][j].push_back({ i, j, sumMass, sumSpeed, d * 2 + 1 });
                    }
                }

 

넣어줄 방향에 따라서 적절히 나눈 파이어볼을 넣는다.

이후에 벡터 복사도 똑같이 해준 후에

 

main 함수로 넘어가서 질량의 총합을 구해주면 된다.

    int result = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 0; k < mapVec[i][j].size(); k++) {
                result += mapVec[i][j][k].mass;
            }
        }
    }

 

 

 

 

 

#결론

 

어려워하지 말고 천천히 구현해보도록 하자.

파이어볼의 정보 기록을 위해서 3차원 벡터를 사용하는 연습을 하기 좋은 문제라고 생각한다.

 

또한 이렇게 긴 구현 문제에서는 

내가 구현해야 될 요소들을 잘 정리하고 설계한 뒤에

 

구현에 차분히 집중하는 연습을 하도록 하자.