[백준/Baekjoon] 20057 마법사 상어와 토네이도 C++ :: Implementation

https://www.acmicpc.net/problem/20057

20057번: 마법사 상어와 토네이도

---

1. Logic

달팽이 탐색 부분은 2중 for문을 돌려서 확인하고 움직이는 칸수가 총 2번씩 반복된다는 규칙은 쉽게 찾았지만 저 좌표에 따라 비율 계산을 어떻게 해야하나 고민을 많이했고 아래의 블로그에서 광명을 찾아버렸다.. 댓글을 보니 나 말고도 여러 사람이 광명을 찾고 간듯..? 풀다가 막혀서 블로그를 찾아들어온 과거의 나 같은 사람들을 위해 아래에 블로그 링크를 걸어놓을게요. 

[ 백준 20057 ] 마법사 상어와 토네이도 (C++)

 

위의 블로그와 내가 푼 풀이를 합쳐서 문제 풀이에 대한 요약을 해보자면

1. 각 위치별 모래의 양을 계산하는 퍼센트를 좌표에 저장해놓는다.

2. 이동거리를 2번씩 반복해야 하기 때문에 2중 for문을 통해 2번씩 반복해야하는 칸수를 반복문으로 돈다.

1. 모래를 저장한 좌표에 따른 퍼센테이지와 매칭시켜 모래를 배분한다.
2. 나머지 남은 모래를 a좌표로 이동한다.

3. 방향을 바꿔주고 이동해야할 칸수를 1 늘려준다.

4. 만약 다 돌고 마지막 1줄을 남겨놨으면(= 이동해야 할 칸수가 n개 일때) n개에 대해서만 모래를 이동시켜주고 정답을 출력한다.

위와 같은 수도 로직으로 표현할 수 있다.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

int n;
int ans = 0;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int dirdx[4][10] = {
    {-3, -1, -2, -1, 0, -1, -2, -1, 0, -2},
    {0, -2, -1, -1, -1, 2, 1, 1, 1, 0},
    {3, 1, 2, 1, 0, 1, 2, 1, 0, 2},
    {0, -2, -1, -1, -1, 2, 1, 1, 1, 0}
};

int dirdy[4][10] = {
    {0, -2, -1, -1, -1, 2, 1, 1, 1, 0},
    {3, 1, 2, 1, 0, 1, 2, 1, 0, 2},
    {0, -2, -1, -1, -1, 2, 1, 1, 1, 0},
    {-3, -1, -2, -1, 0, -1, -2, -1, 0, -2}
};

int persentage[9] = {5, 2, 10, 7, 1, 2, 10, 7, 1};
int graph[501][501];

void moveSand(int yy, int xx, int dir) {
    int x = xx + dx[dir];
    int y = yy + dy[dir];
    if(graph[y][x] == 0) return;
    
    int locA = graph[y][x];
    int temp = locA;
    
    for(int i = 0; i < 9; i++) {
        int nx = xx + dirdx[dir][i];
        int ny = yy + dirdy[dir][i];
        int persent = persentage[i];
        int calc = (temp*persent)/100;
        
        if(nx < 0 || nx >= n || ny < 0 || ny >= n) ans += calc;
        else graph[ny][nx] += calc;
        
        locA -= calc;
    }
    
    int aX = xx + dirdx[dir][9];
    int aY = yy + dirdy[dir][9];
    
    if(aX < 0 || aX >= n || aY < 0 || aY >= n) ans += locA;
    else graph[aY][aX] += locA;
    graph[y][x] = 0;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }
    
    int x = n/2;
    int y = n/2;
    int moveDist = 1;
    int dir = 0;
    
    while(true) {
        
        for(int i = 0; i < 2; i++) {
            for(int j = 0; j < moveDist; j++) {
                moveSand(y, x, dir);
                x = x+dx[dir];
                y = y+dy[dir];
            }
            dir = (dir+1)%4;
        }
        moveDist++;
        if(moveDist == n) {
            for(int i = 0; i < moveDist; i++) {
                moveSand(y, x, dir);
                x = x + dx[dir];
                y = y + dy[dir];
            }
            break;
        }
    }
    cout << ans;
}

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐