[코드트리] 2차원 바람 C++

문제

https://www.codetree.ai/missions/2/problems/The-2D-wind-blows?&utm_source=clipboard&utm_medium=text

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

 

계획 세우기

어제의 1차원 바람이랑 비슷한데, 조금 더 어렵게 바꾼 느낌이다.

각 바람에 대해 아래 과정을 수행해주면 될 것 같다.

 

1. 주어진 범위 대로 shift 진행(총 4단계, 아래 그림 참고)

 

 

2. 바꾼 뒤 주어진 범위에서 자신과 상하좌우칸의 평균을 배열에 저장

동시에 일어남=순차적으로 일어나면 바뀐 값에 영향을 받지만, 동시에 일어나기 때문에 원본 배열(회전 후)의 값으로 평균 값을 내야 함

• arr[i][j] + ij의 상하좌우 값을 더함. 배열의 범위를 벗어나면 더하면 안 되기 때문에 몇 개를 더했는지 cnt로 세기
• 평균 구하기 float avg = sum/cnt;
• 소수점을 버려서 배열에 저장해야 하므로 static_cast<int>(avg)로 int 형변환 해주고, avgArr[i][j]에 저장
  
  • static_cast<int>(변수명)은 cpp스타일 형변환. c스타일의 (int)(변수명) 형변환보다 안전하고 명확하다.
  • c스타일의 경우 변환할 수 없는 자료형으로 변환을 시도할 수 있기 때문에 위험함
  • https://learn.microsoft.com/en-us/cpp/cpp/static-cast-operator?view=msvc-170
•  
•  avg 배열을 arr의 r1, c1, r2, c2 범위에 복사해준다.

 

 

풀이

#include <iostream>

using namespace std;

int n, m, q;
int building[101][101];
int wind[101][4]; // 1-base {{r1, c1, r2, c2}, ...}

void GetInput(){
    cin >> n >> m >> q;
    // input n*m arr
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> building[i][j];
        }
    }
    // input wind
    for(int i=0; i<q; i++){
        cin >> wind[i][0] >> wind[i][1] >> wind[i][2] >> wind[i][3];
    }
}

void PrintArr(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cout << building[i][j] << " ";
        }
        cout << '\n';
    }
}

//직사각형 영역의 경계에 있는 숫자들을 시계 방향으로 한 칸씩 shift
void RotateShift(int r1, int c1, int r2, int c2){
    // r1줄 오른쪽으로 한 칸씩 옮기기 ->
    int r1c2= building[r1][c2];
    for(int i=c2; i>c1; i--){
        building[r1][i]= building[r1][i-1];
    }
    
    // c2줄 아래로 한 칸씩 옮기기
    int r2c2 = building[r2][c2];
    for(int i=r2; i>r1+1; i--){
        building[i][c2]=building[i-1][c2];
    }
    building[r1+1][c2] = r1c2;

    int r2c1=building[r2][c1];
    for(int i=c1; i<c2-1; i++){
        building[r2][i]= building[r2][i+1];
    }
    building[r2][c2-1]= r2c2;

    for(int i=r1; i<r2-1; i++){
        building[i][c1]=building[i+1][c1];
    }
    building[r2-1][c1] =r2c1;
}

// 직사각형 영역 내에 있는 각각의 숫자들의 값이 [현재 칸에 적혀있는 숫자 + 인접한 곳에 적혀있는 숫자들의 평균 값]으로 바뀌게 됩니다.
// 이 과정은 순차적으로 일어나는 것이 아니라 동시에 일어납니다. 평균 계산시에는 항상 버림하여 정수값이 나오도록 합니다.
void ChangeToAvg(int r1, int c1, int r2, int c2){
    // 좌(0, -1) 상(-1, 0) 하(1, 0) 우(0, 1)
    int dx[4] = {0, -1, 1, 0};
    int dy[4] = {-1, 0, 0, 1};

    // 자신+상하좌우 살피면서 avgArr 채우기
    int avgArr[r2-r1+1][c2-c1+1]={0, };

    for(int i=r1; i<=r2; i++){
        for(int j=c1; j<=c2; j++){
            int sum=building[i][j], cnt=1;
            
            for(int dir=0; dir<4; dir++){
                int x= i+dx[dir], y=j+dy[dir];
                // 범위를 넘어가면 continue;
                if(x<0 || x>=n || y<0 || y>=m) continue;
                sum+=building[x][y];
                cnt++;
            }

            float avg = sum/cnt;
            avgArr[i-r1][j-c1]= static_cast<int>(avg);
        }
    }


    // avgArr의 원소를 building 배열에 복사
    for(int i=r1; i<=r2; i++){
        for(int j=c1; j<=c2; j++){
            building[i][j] = avgArr[i-r1][j-c1];
        }
    }
}

void WindStart(){
    for(int i=0; i<q; i++){
        // 1based라서 1 빼줘야 함
        int r1 = --wind[i][0], c1 = --wind[i][1], r2=--wind[i][2], c2=--wind[i][3];
        RotateShift(r1, c1, r2, c2);
        ChangeToAvg(r1, c1, r2, c2);
    }
}

int main() {
    GetInput();

    WindStart();

    PrintArr();
    return 0;
}