[코드트리 조별과제] 십자 모양의 지속적 폭발 C++ 풀이

---

알고리즘 분류

• 시뮬레이션

---

문제 설명

---

입력 설명

첫 번째 줄에는 격자의 크기를 나타내는 n과 폭탄을 터뜨릴 횟수 m이 공백을 사이에 두고 주어집니다.

두 번째 줄 부터는 n개의 줄에 걸쳐 각 행에 해당하는 n개의 숫자가 공백을 사이에 두고 주어집니다.

그 다음 줄 부터는 m개의 줄에 걸쳐 폭탄을 터뜨릴 열의 위치 c가 순서대로 주어집니다. (1 ≤ c ≤ n)

• 1 ≤ n ≤ 200
• 1 ≤ m ≤ 10

---

출력 설명

m번에 걸쳐 폭탄이 터지고 중력이 작용한 것을 반복한 이후의 결과를 출력합니다.

n개의 줄에 걸쳐 각 행에 해당하는 n개의 숫자를 공백을 사이에 두고 출력합니다. 만약 해당 위치에 아무 숫자도 적혀있지 않은 경우라면 0을 출력합니다.

---

예제 입력

4 4
1 1 2 3
3 2 2 3
3 1 6 2
4 5 4 4
2
2
2
2

 

4 3
1 2 4 3
3 2 2 3
3 1 6 2
4 5 4 4
2
2
2

---

예제 출력

0 0 0 0
0 0 0 3
1 0 2 3
3 0 6 2

 

0 0 0 0
0 0 0 3
3 0 2 3
3 0 6 2

---

아이디어

입력받은 열에서 0번째 행부터 0이 아닌 숫자가 있는지 탐색한다.

0이 아닌 숫자를 발견하면 해당 숫자만큼의 범위로 폭발한다.

이후 중력 방향으로 블럭을 이동시킨다.

---

알고리즘

bomb 함수에서는 입력받은 열에 0이 아닌 숫자가 있는지 탐색한 후 존재한다면 해당 칸의 숫자만큼의

상하좌우의 범위를 모두 0으로 채운다.

만약 범위가 3칸이고 입력받은 열이 c라면

z를 0 ~ 2 까지 증가시키며 vec[i+z][c], vec[i-z][c], vec[i][c+z], vec[i][c-z]가 vector 범위를 벗어나지 않는지 체크하며 전부 0을 넣는다.

gravity 함수에서는 폭발 이후의 vector를 중력 방향으로 블럭이 떨어지도록 재정렬한다.

임시 vector nvec을 선언한다.

행과 열 모두 0 ~ n까지 반복하는 2중 for문을 구성하여 vec[j][i]가 0이라면 nvec[i]에 push_back() 한다.

이후 행과 열 모두 0 ~ n까지 반복하는 2중 for 문을 구성하여 vec[j][i]가 0이 아니라면 nvec[i]에 push_back() 한다.

이후 행과 열 모두 0 ~ n까지 반복하는 2중 for 문을 구성하여 nvec[i][j]를 vec[j][i]에 다시 넣어주면

vec는 중력 방향으로 숫자가 정렬된다. 이를 출력한다.

---

코드

#include <iostream>
#include <vector>
using namespace std;
void printvec(vector<vector<int>> &vec, int n)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cout<<vec[i][j]<<" ";
        }
        cout<<"\n";
    }
    cout<<"\n";
}
vector<vector<int>>& bomb(vector<vector<int>> &vec, int c, int n)
{
    for(int i=0; i<n; i++)
    {
        if(vec[i][c] != 0)
        {
            int num = vec[i][c];
            for(int z=0;z<num;z++)
            {
                if(0 <= i-z  && vec[i-z][c] != 0) vec[i-z][c] = 0;
                if(i+z < n && vec[i+z][c] != 0) vec[i+z][c] = 0;
                if(0 <= c-z && vec[i][c-z] != 0) vec[i][c-z] = 0;
                if(c+z < n && vec[i][c+z] != 0) vec[i][c+z] = 0;
            }
            break;
        }
    }
    return vec;
}

vector<vector<int>>& gravity(vector<vector<int>> &vec, int n)
{
    vector<vector<int>> nvec(n, vector<int>());
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(vec[j][i] == 0) nvec[i].push_back(vec[j][i]);

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(vec[j][i] != 0) nvec[i].push_back(vec[j][i]);

    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            vec[j][i] = nvec[i][j];
    return vec;
}
int main() {
    int n, m;
    cin>>n>>m;
    vector<vector<int>> vec(n, vector<int>(n));
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>vec[i][j];
    for(int z=0;z<m;z++)
    {
        int c;
        cin>>c;
        vec = gravity(bomb(vec, c-1, n), n);
    }
    printvec(vec, n);
    return 0;
}

---

후기

문제 링크 -> https://www.codetree.ai/missions/2/problems/cross-shape-continuous-bomb?&utm_source=clipboard&utm_medium=text

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

 

 

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!