백준 21610 (삼성 SW 역량평가 기출) - 마법사 상어와 비바라기

 이 포스팅은 삼성 GIST 모터 트랙 대비 과정에서 풀었던 기출 문제에 대한 글입니다. 모두 백준에 공개된 문제들만 있으며, SW Expert Academy에서만 다루는 문제들은 저작권 문제로 업로드 되지 않습니다.

---

1. 문제 내용

문제 링크: https://www.acmicpc.net/problem/21608

문제 난이도: GOLD V

2. 접근법

• 문제가 조금 복잡하긴 하지만 조금만 읽어보면 단순 구현 문제임을 알 수 있음.
• 한 문장씩 차근차근 읽어보며 구현하면 됨.

3. 풀이 코드

/*
주의할 점)
문제에선 구름이 사라지고 물복사버그를 쓴다고 되어있지만
'2에서 물이 증가한 칸'에 대해서만 마법을 쓰고, 이는 구름이 있던 자리이므로
마법을 쓰고 나서 구름 행렬을 초기화해야 함!

그리고 5번에서 구름을 새로 만들 때도 '구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다'는 조건이 있으므로 
구름이 있던 자리 정보를 마찬가지로 알아야 함!

1 -> 2 -> 4 -> 3과5(동시) 순으로 실행해야 함!

*/
#include <iostream>

using namespace std;

int N, M;
bool clouds[50][50];
int buckets[50][50];
int moves[100][2];
int dx[8] = { 0, -1, -1, -1, 0, 1, 1,  1};
int dy[8] = {-1, -1,  0,  1, 1, 1, 0, -1};

//debugging functions
void displayClouds() {
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) cout << clouds[i][j] ? 1 : 0 << ' ';
            cout << '\n';
    }
}

//debugging
void displayBuckets() {
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) cout << buckets[i][j] << ' ';
        cout << '\n';
    }
}
        


// 1번 항목 시뮬레이션 함수
void moveClouds(int d, int s) {
    
    bool newClouds[50][50] = {false, };
    
    //이동
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            
            //이동 후 좌표 계산
            if(clouds[i][j]) {
                int nx = (((i + dx[d - 1] * s) % N) + N) % N; // 음/양 모든 경우에 사용 가능한 좌표 계산식!
                int ny = (((j + dy[d - 1] * s) % N) + N) % N;
                
                newClouds[nx][ny] = true;
            }
            
        }
    }    
    
    //복사
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            clouds[i][j] = newClouds[i][j];
        }
    } 
    return ;
}



int main() {
    
    //input
    cin >> N >> M;
    for(int i = 0; i < N; i++) {
        for(int j =0; j < N; j++) {
            cin >> buckets[i][j];
        }
    }
    for(int i = 0; i < M; i++) {
        cin >> moves[i][0] >> moves[i][1];
    }
    
    //비바라기로 초기 구름 생성
    clouds[N-1][0] = true;
    clouds[N-1][1] = true;
    clouds[N-2][0] = true;
    clouds[N-2][1] = true;
    
    //시뮬레이션 시작
    for(int m = 0; m < M; m++) {
        
        //1. 구름 이동
        moveClouds(moves[m][0], moves[m][1]);
        
        //debugging
        //cout << "===" << m << "번째 이동 후 구름 위치===" << '\n';
        //displayClouds();
        
        //2. 구름에서 비 내리기
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(clouds[i][j]) {
                    buckets[i][j]++;
                }
            }
        }
        
        //debugging
        //cout << "===" << m << "번째 비 내리기===" << '\n';
        //displayBuckets();
        
        //4. 물이 증가한 칸에 복사버그마법 시전
        //모든 곳에 비가 다 내리고 나야 제대로 계산 가능하므로 
        // 2번과 별도의 for문으로 돌려야 함!
        
        int add_amount[50][50] = {0, }; //마법으로 인한 물 증가량 행렬
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                
                //물이 증가한 칸에만 복사버그마법 시전
                if(clouds[i][j]) {

                    //대각선이므로 2, 4, 6, 8번 방향만 확인
                    for(int k = 1; k < 8; k += 2) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        
                        //유효한 칸인 경우 바구니 당 1씩 증가
                        if(nx >= 0 && nx < N && ny >= 0 && ny < N && buckets[nx][ny] > 0) add_amount[i][j] += 1;
                    }
                }
            }
        }
        
        // 실제로 증가한 양을 더하는 것도 증가량을 다 구하고 나서 별도의 for문으로 돌려야 함
        // 물이 0인 곳이 더해서 1이상이 되버리면 다른 칸 복사마법 계산에 영향을 주기 때문
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                
                buckets[i][j] += add_amount[i][j];
            }
        }
        //debugging
        //cout << "===" << m << "번째 복사마법===" << '\n';
        //displayBuckets();
        
        //3 & 5 기존 구름 제거 및 새 구름 생성
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                
                if(!clouds[i][j] && buckets[i][j] >= 2) {
                    clouds[i][j] = true;
                    buckets[i][j] -= 2;
                }
                else if(clouds[i][j]) clouds[i][j] = false;
            }
        } 
        
        //debugging
        //cout << "===" << m << "번째 새 구름===" << '\n';
        //displayClouds();
        
        
        //debugging
        //cout << "===" << m << "번째 단계 완료===" << '\n';
        //displayBuckets();
    }
    
    // M번의 이동이 모두 끝난 후 점수 계산
    int total_score = 0;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++){
            total_score += buckets[i][j];
        }
    }
    cout << total_score << '\n';
    return 0;
}

4. 중요 포인트

• vector::clear() 함수: new는 포인터에만 사용 가능하므로 최대/최소 후보 저장할 땐 clear 사용할 것!
• 배열에서의 인덱스와 고유 번호 모두 이곳저곳에 사용된다면, 하나를 알 때 나머지를 쉽게 접근 가능하도록 인덱스 배열을 추가로 하나 더 둘 것! N이 작다면 적은 공간복잡도로 O(1)의 속도를 두 요소 모두의 접근에 사용 가능!