[BaekJoon/백준] 21610번 마법사 상어와 비바라기

f

재미있었는데 힘들었다..

 

 

키포인트는 이러했다.

 

1. 구름의 위치가 이동할 때, 배열이 연결되어 있다는 점을 인지

-> 적절한 식을 구성해주어야 한다.

 

2. 물복사를 시전할 때, 찾음과 동시에 바로 값을 갱신해버리면, 이후에 다른 위치의 물복사를 할 때 값 계산에 오류가 생길 수 있음

-> 물복사 할 위치를 미리 계산만 해 놓았다가, 나중에 한꺼번에 갱신

 

 

나는 구름의 위치를 저장하는데 set 알고리즘을 사용했고,

한 phase 마다

처음 구름, 이동된 구름, 새로 생성된 구름

이렇게 세 개의 set을 결국 사용하게 되었다.

#include <iostream>
#include <set>
#include <vector>

using namespace std;


int N, M;

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

int tx[4] = {-1, -1, 1, 1};
int ty[4] = {-1, 1, -1, 1};

set<pair<int, int>> cloud;


void perform(int dir, int len, vector<vector<int>>& v) {
    
    
    set<pair<int, int>> moved_cloud; // cloud가 이동하여 moved_cloud 위치를 게산할 것임
    
    // 1 ~ 2 번
    for(auto c : cloud) { // auto c는 '복제' 다 !!
                
        c.first = c.first + mx[dir - 1] * len; // 방향도 0 base 이니까 -1 해줌
        c.second = c.second + my[dir - 1] * len; // 방향도 0 base 이니까 -1 해줌
        
        
        c.first = c.first % N;
        c.first = c.first >= 0 ? c.first : N - (abs(c.first) % N); // 음수면 처리
        
        c.second = c.second % N;
        c.second = c.second >= 0 ? c.second : N - (abs(c.second) % N); // 음수면 처리

        v[c.first][c.second]++; // 구름이 이동한 뒤 해당 위치에 물 증가
        
        moved_cloud.insert({c.first, c.second});
    }
    
    cloud = moved_cloud; // cloud 위치 갱신
    
    
    // 출력해봄
//    for(int i = 0; i < N; i++) {
//        for(int j = 0; j < N; j++) {
//            cout << v[i][j] << " ";
//        }
//        cout << "\n";
//    }
//
//    cout << "\n";
    
    
    
    //4 번
    // 물 복사에 대한 정보를 저장할 벡터
    vector<vector<int>> copy_water(N, vector<int>(N, 0));
    
    for(auto c : cloud) {
                
        for(int i = 0; i < 4; i++) {
            
            int xx = c.first + tx[i];
            int yy = c.second + ty[i];
            
            
            if(xx < 0 || xx >= N || yy < 0 || yy >= N)
                continue;
            
            
            if(v[xx][yy] > 0) // 대각선에 물이 채워져 있다 = 물복사
                copy_water[c.first][c.second]++; // 물복사 할 수치 미리 저장. 여기서 바로 갱신해버리면, 이후 책정에 오류가 생길 수 있기에.
            
        }
        
    }
    
    // 저장해놨던 물 복사 위치들에 대해 값 갱신
    for(int i  = 0 ; i < N; i++) {
        for(int j = 0; j < N; j++) {
            if(copy_water[i][j] > 0)
                v[i][j] += copy_water[i][j];
        }
    }
    
    
    // 출력해봄
//    for(int i = 0; i < N; i++) {
//        for(int j = 0; j < N; j++) {
//            cout << v[i][j] << " ";
//        }
//        cout << "\n";
//    }
//
//    cout << "\n";
//
//
    
    // 새로 생길 cloud의 위치들을 저장할 new_cloud
    set<pair<int, int>> new_cloud;
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
                        
            // set의 find가 값을 찾을 수 없으면, end()와 같은 iterator를 리턴한다.
            if(v[i][j] >= 2 && cloud.find({i, j}) == cloud.end()) {
                
                new_cloud.insert({i, j});
                v[i][j] -= 2;
            }
            
            
        }
    }
    
    // cloud 갱신
    cloud = new_cloud;
    
    
    // 출력해봄
//    for(int i = 0; i < N; i++) {
//        for(int j = 0; j < N; j++) {
//            cout << v[i][j] << " ";
//        }
//        cout << "\n";
//    }
//
//    cout << "\n";
//

    
}

int main() {

    int dir, len;

    cin >> N >> M;

    
    vector<vector<int>> v(N, vector<int>(N, 0));


    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> v[i][j];
        }
    }
    

    
    // 문제는 1 base이고, 나는 0 base 니까 -1씩 해줬음.
    cloud.insert({N - 1, 0}); cloud.insert({N - 1, 1});
    cloud.insert({N - 2, 0}); cloud.insert({N - 2, 1});
    
    while(M--) {


        cin >> dir >> len; // 방향과 길이 입력
        
        perform(dir, len, v);

    }
    
    int AA = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            AA += v[i][j];
        }
    }
    cout << AA << "\n";




}

 

그리고 문제를 풀면서 알게된 점은 두 가지 있다.

 

1.

-1 % 5 => -1
-2 % 5 => -2
-5 % 5 => 0

 

2. for(auto x : list) 구문에서, x는 '복사'된 상태다.

x를 갱신한다고 해서 list 내부가 정말 갱신되지 않는다.

 

3. set의 iterator로는 원소 값 변경이 불가능하다.

-> set의 특성이다. erase 후 insert 해야한다.

 

4. set 자료구조에서 find() 사용 시, 원소가 발견되지 않으면 end() 함수와 같은 iterator를 리턴하며

발견될 시에는 해당 위치의 iterator를 리턴한다. 

 

5. 디버거는 꼭 필요하다........

 

---

 

풀만 했는데, 확실한건 매 과정을 출력하면서 디버깅도 할 수 있었기에 풀 수 있었다.

그게 안되면 절대 못 풀었을 듯.

 

started at 22:13

ended at 23:38