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

---

알고리즘 분류

• 시뮬레이션

---

문제 설명

---

입력 설명

첫 번째 줄에는 격자의 크기를 나타내는 n이 주어집니다.

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

그 다음 줄에는 폭탄이 터질 중심 위치의 정보를 나타내는 (r, c) 값이 공백을 사이에 두고 주어집니다. 이는 r행 c열이 중심 위치임을 의미합니다.

• 1 ≤ n ≤ 200
• 1 ≤ r, c ≤ n

---

출력 설명

폭탄이 터지고 나서 중력이 작용한 뒤의 결과를 출력합니다.

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

---

예제 입력

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

 

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

---

예제 출력

1 0 0 0
3 2 0 3
3 1 0 2
4 5 4 4

 

0 0 0 0
1 2 0 3
3 2 0 3
4 5 0 4

---

아이디어

주어진 좌표로 이동해서 들어있는 숫자만큼 상하좌우를 모두 0으로 변경한다.

이후 1열씩 탐색하여 아래 방향으로 숫자를 내린다.

---

알고리즘

주어진 좌표로 이동해서 들어있는 숫자만큼 상하좌우를 모두 0으로 변경한다.

2차원 temp과 1차원 temp 배열을 선언하여 기존 배열을 1열씩 탐색하여 그 값이 0이 아니라면 1차원 temp 배열에 넣는다.

이후 1차원 temp 배열의 값을 올바른 2차원 temp 배열에 옮긴다.

이를 n번 반복하면 중력 방향으로 숫자가 내려간 2차원 temp 배열이 완성되므로 이를 출력한다.

---

코드

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> gravity(vector<vector<int>> &vec, int n)
{
    vector<vector<int>> temp_2d(n+1, vector<int>(n+1,0));
    for(int j=1;j<=n;j++)
    {
        vector<int> temp(1,0);
        for(int i = 1; i <= n; i++)
            if(vec[i][j] != 0) temp.push_back(vec[i][j]);
        while(temp.size() < n+1)
            temp.insert(temp.begin(),0);
        for(int i = 1; i <= n; i++)
            temp_2d[i][j] = temp[i];
    }
    return temp_2d;
}
int main() {
    int n, r, c;
    cin>>n;
    vector<vector<int>> vec(n+2,vector<int>(n+2,-1));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>vec[i][j];
    cin>>r>>c;
    int boom = vec[r][c];
    for(int i=0;i<boom;i++)
    {
        if(0 < r+i && r+i <= n && vec[r+i][c] != -1) vec[r+i][c] = 0;
        if(0 < r-i && r-i <= n && vec[r-i][c] != -1) vec[r-i][c] = 0;
        if(0 < c+i && c+i <= n &&vec[r][c+i] != -1) vec[r][c+i] = 0;
        if(0 < c-i && c-i <= n &&vec[r][c-i] != -1) vec[r][c-i] = 0;
    }
    vec = gravity(vec, n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<vec[i][j]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

---

후기

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

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

 

배열은 자주 다뤄봤지만, 격자 안에서 터지고 떨어지는 경우는 처음 다뤄봐서 신선해서 좋았다.

---

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

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