[ 백준 20057 ] 마법사 상어와 토네이도 (C++) - 시뮬레이션

---

🔗 문제 링크

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

---

💡 문제 풀이 및 해석

문제의 핵심은 일정 비율로 모래가 흩날리는 것인데, 기존에 BFS 문제에서 next를 정해두고 상하좌우로 이동하는 것을 조금 늘렸다고 생각하면 된다. 해당 코드는 다음과 같다. 퍼지는 것은 9개인데, 왜 10개냐면 마지막은 문제에서 설명상 알파의 위치이다. 그리고 퍼지는 위치에 맞게 percent도 정해놨다.

int next_x[][10] = {
    {0, -1, 1, -2, -1, 1, 2, -1, 1, 0}, {2, 1, 1, 0, 0, 0, 0, -1, -1, 1}, {0, -1, 1, -2, -1, 1, 2, -1, 1, 0},
    {-2, -1, -1, 0, 0, 0, 0, 1, 1, -1}
};
int next_y[][10] = {
    {-2, -1, -1, 0, 0, 0, 0, 1, 1, -1}, {0, -1, 1, -2, -1, 1, 2, -1, 1, 0}, {2, 1, 1, 0, 0, 0, 0, -1, -1, 1},
    {0, -1, 1, -2, -1, 1, 2, -1, 1, 0}
};
int percent[] = {5, 10, 10, 2, 7, 7, 2, 1, 1};

퍼지는 알고리즘은 위 코드를 보고, 기존 BFS를 잘 생각해보면 구현하는 것은 쉬울 거라고 생각한다. (나는 모래를 더해야 하는데, 한 곳을 =로 초기화를 시켜버려서 못찾고 풀다가 2시간이 넘게 걸렸다.)

나머지는 토네이도 돌듯이 돌아가게 하는 알고리즘만 작성하면 끝인데, 패턴을 보면 1칸 * 2, 2칸 * 2, 3칸 * 2 ... 이런 식의 패턴이다. 따라서, 매번 정해진 칸수를 이동하면 방향을 틀고, 방향을 2번 틀으면 칸수를 +1해주고, 방향은 다시 2번 틀 수 있게 해주면 된다.

---

⭐️ 정답 코드 및 설명

#include<iostream>

using namespace std;

int N, answer = 0;
int Map[500][500];
int next_x[][10] = {
    {0, -1, 1, -2, -1, 1, 2, -1, 1, 0}, {2, 1, 1, 0, 0, 0, 0, -1, -1, 1}, {0, -1, 1, -2, -1, 1, 2, -1, 1, 0},
    {-2, -1, -1, 0, 0, 0, 0, 1, 1, -1}
};
int next_y[][10] = {
    {-2, -1, -1, 0, 0, 0, 0, 1, 1, -1}, {0, -1, 1, -2, -1, 1, 2, -1, 1, 0}, {2, 1, 1, 0, 0, 0, 0, -1, -1, 1},
    {0, -1, 1, -2, -1, 1, 2, -1, 1, 0}
};
int percent[] = {5, 10, 10, 2, 7, 7, 2, 1, 1};

void Init() {
    cin >> N;
    for (int x = 1; x <= N; x++) {
        for (int y = 1; y <= N; y++) {
            cin >> Map[x][y];
        }
    }
}

bool isIn(int x, int y) {
    if (x > 0 && x <= N && y > 0 && y <= N) return true;
    return false;
}

void SpreadSand(int dir, int x, int y) {
    int sand = Map[x][y];
    int sandTemp = Map[x][y];
    int spreadSand;
    for (int i = 0; i < 9; i++) {
        spreadSand = sandTemp * percent[i] / 100;
        int nx = x + next_x[dir][i], ny = y + next_y[dir][i];
        if (isIn(nx, ny)) Map[nx][ny] += spreadSand;
        else answer += spreadSand;
        sand -= spreadSand;
    }
    int nx = x + next_x[dir][9], ny = y + next_y[dir][9];
    if(isIn(nx,ny)) Map[nx][ny] += sand;
    else answer += sand;
    Map[x][y] = 0;
}

void Move(int dir, int x, int y, int turnCnt, int dirCnt, int dirNum) {
    if (y == 0 || x == 0) {
        return;
    }

    if (dir == 0) y--;
    else if (dir == 1) x++;
    else if (dir == 2) y++;
    else if (dir == 3) x--;

    SpreadSand(dir, x, y);

    dirCnt--;
    if (dirCnt == 0) {
        turnCnt--;
        dirCnt = dirNum;
        dir++;
    }

    if (turnCnt == 0) {
        turnCnt = 2;
        dirCnt = ++dirNum;
    }
    dir %= 4;
    Move(dir, x, y, turnCnt, dirCnt, dirNum);
}

int main() {
    Init();
    Move(0, (N + 1) / 2, (N + 1) / 2, 2, 1, 1);
    cout << answer + Map[1][0]<< endl;
    return 0;
}

---

🤔 문제 후기

문제 풀이 방법은 매우 쉬웠다. 다만, 실수없이 그리고 처음에 문제를 보고 바로 생각하기에는 비슷한 유형을 풀어보지 않았으면 좀 어렵지 않았나 싶다. 생각은 했는데, 실수를 하면 실수를 찾기도 생각보다 어려운 문제였다. 알파 위치도 범위 안에 있는지 체크해줘야 했는데, 까먹고 안한 점 그리고 +=sand 인데, =sand로 실수를 하고, 끝까지 모른 점 등이 생각보다 많은 문제였다.