[BaekJoon/백준] 20058번 마법사 상어와 파이어스톰

 

이 문제를 풀며 느낀점 세가지

 

 

1. 배열 회전 한번 더 보기

2. SCC 관련 문제들도 한번 더 보기(삼성기출 특히)

3. 나중에 바꿀생각하지말고, 첨부터 뭘 어떻게 지칭할 것인지 명확히 약속 정의하고 코딩 시작해야 함의 중요성..

 

 

3번의 경우엔,, 한 변의 길이를 정의하는 변수를 m으로 할지, 2^m으로 할지 명확히 하지 않은 점에서 비롯되어 문제가 생겼었다.

 

그리고 처음 제출할 때 시간초과가 떴었는데,, 이유는 pow함수의 반복적인 호출이 오버헤드로 누적된 것이었다.

pow 함수의 오버헤드가 시간초과의 원인이었다. 그래서 변수를 따로 선언해준 뒤에, 한번만 pow값을 구한뒤 재사용했따.

 

#include <iostream>
#include <cmath>
#include <vector>
#include <cstring>

using namespace std;

int N, Q;

int POW_N; // pow가 오버헤드가 컸던 거다.. 이렇게 변수로 저장하고 있으니 통과되었다.

int MAP[64][64]; // 오랜만에 배열로
int T_MAP[64][64]; // 갱신을 위한 임시배열

bool MELTING_SPOT[64][64];
bool VISIT[64][64];

int MAX_GROUND = 0, GROUND = 0;



int mx[4] = {-1, 1, 0, 0};
int my[4] = {0, 0, 1, -1};



// 90도 회전
void rotate(int sx, int sy, int m) {
    
    
    
    for(int i = 0; i < m; i++) {
        
        for(int j = 0; j < m; j++) {
            
            T_MAP[sx + i][sy + j] = MAP[sx + (m - j - 1)][sy + i];
            
        }
    }
    
}

void divide_and_conquer(int sx, int sy, int m, int mn) { // m : 목표치 길이, mn : 현재 길이
    
    
    if(m == mn) {
        
        rotate(sx, sy, m);
        
        
    } else {
        
        for(int i = 0; i < 2; i++) {
            for(int j = 0; j < 2; j++) {
                
                divide_and_conquer(sx + ((mn / 2) * i), sy + ((mn / 2) * j), m, (mn / 2));
                
            }
        }
    }
    
    
}

// 녹은 뒤 얼음 수까지 리턴해줌.
int melt() {
    
    
    memset(MELTING_SPOT, 0, sizeof(MELTING_SPOT));
    
    
    for(int i = 0; i < POW_N; i++) {
        for(int j = 0; j < POW_N; j++) {
            
            
            int COUNT = 0;

            for(int k = 0; k < 4; k++) {
                
                int xx = i + mx[k];
                int yy = j + my[k];
                
                
                // 여기 POW_N 으로 비교 안하고,, N으로 비교한게 문제된걸 못찾아서 시간오래 잡아먹었다.
                // 코딩 시작할 때부터, 규칙이랑 정의 명확히 정해놓고 가는 것의 중요성..
                if(xx < 0 || xx >= POW_N || yy < 0 || yy >= POW_N)
                    continue;
                
                
                
                if(MAP[xx][yy] > 0)
                    COUNT++;
                
            }
            
            if(COUNT < 3) {
                MELTING_SPOT[i][j] = true;
            }
            
            
            
            
            
        }
    }
    
    int TOTAL = 0;
    
    for(int i = 0; i < POW_N; i++) {
        for(int j = 0; j < POW_N; j++) {
            if(MELTING_SPOT[i][j] && MAP[i][j] > 0) // 얼음이 0에서 음수로 더 떨어지지 않게 두번쨰 조건 넣어줘야함.
                MAP[i][j]--;
            
            TOTAL += MAP[i][j];
        }
    }
    
    return TOTAL;
}

void dfs(int sx, int sy) {
    
    VISIT[sx][sy] = true;
    GROUND++;
    
    
    
    for(int i = 0; i < 4; i++) {
        int xx = sx + mx[i];
        int yy = sy + my[i];
        
        
        if(xx < 0 || xx >= POW_N || yy < 0 || yy >= POW_N)
            continue;
        
        if(MAP[xx][yy] != 0 && !VISIT[xx][yy])
            dfs(xx, yy);
    }
    
}

int main() {
    
    int tmp;
    
    cin >> N >> Q;
    
    POW_N = pow(2, N);
    
    
    for(int i = 0; i < POW_N; i++) {
        for(int j = 0; j < POW_N; j++) {
            
            cin >> MAP[i][j];
        }
    }
    
    int r;
    
    while(Q--) {
        

        
        cin >> tmp;
        
        memset(T_MAP, 0, sizeof(T_MAP));

        
        divide_and_conquer(0, 0, pow(2, tmp), POW_N);
        
        
        memmove(MAP, T_MAP, sizeof(T_MAP));
        
        // 여기서 시간 터지겠네.
        r = melt();
        
    }
    
//
//        for(int i = 0; i < POW_N; i++) {
//            for(int j = 0; j < POW_N; j++) {
//                cout << MAP[i][j] << " ";
//            }
//            cout << "\n";
//        }
//
//
    
    
    for(int i = 0; i < POW_N; i++) {
        for(int j = 0; j < POW_N; j++) {
            
            if(!VISIT[i][j] && MAP[i][j] != 0) {
                GROUND = 0;
                dfs(i, j);
                
                if(MAX_GROUND < GROUND)
                    MAX_GROUND = GROUND;
            }
            
        }
    }
    
    cout << r << "\n" << MAX_GROUND << "\n";
}

 

 

 

그리고 문제를 풀던 중에 궁금한 점이 하나 생겼었다.

 

memmove가 메모리 이동이면, 이동후에 덮어씌면 같이 덮어씌워지나.?

직접 해봤다.

#include <iostream>
#include <cstring>

using namespace std;

int main() {
    
    int MAP[2][2] = {{1, 2}, {3, 4}};
    
    int T_MAP[2][2] = {{5, 6}, {7, 8}};
    
    
    memmove(MAP, T_MAP, sizeof(T_MAP));
    
    memset(T_MAP, 0, sizeof(T_MAP));
    
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            cout << MAP[i][j] << " ";
            
        }
        cout << "\n";
    }
}

/*
OUTPUT

5 6
7 8
*/

그건 아니었다!

 

 

---

 

started at 00:53

ended at 02:35