[BOJ] 백준 20057 마법사 상어와 토네이도

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

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

 Input 

5

0 0 100 0 0

0 0 100 0 0

0 0 0 0 0

0 0 100 0 0

0 0 100 0 0

　 

 Output 

283　

 Input 

9

193 483 223 482 858 274 847 283 748

484 273 585 868 271 444 584 293 858

828 384 382 818 347 858 293 999 727

818 384 727 373 636 141 234 589 991

913 564 555 827 0 999 123 123 123

321 321 321 983 982 981 983 980 990

908 105 270 173 147 148 850 992 113

943 923 982 981 223 131 222 913 562

752 572 719 590 551 179 141 137 731

 

 Output 

22961 

 Input 

5

0 0 0 0 0

0 0 0 0 0

0 100 0 0 0

0 0 0 0 0

0 0 0 0 0

 

 Output 

85

 Input 

7

1 2 3 4 5 6 7

1 2 3 4 5 6 7

1 2 3 4 5 6 7

1 2 3 0 5 6 7

1 2 3 4 5 6 7

1 2 3 4 5 6 7

1 2 3 4 5 6 7

 

 Output 

139 

① 토네이도 이동 처리

토네이도의 특정 방향에서 이동하는 거리는 아래와 같은 규칙이 있습니다.

    N = 3: 1 1 2 2 2

    N = 5: 1 1 2 2 3 3 4 4 4

    N = 7: 1 1 2 2 3 3 4 4 5 5 6 6 6

즉, 1 → N-1까지 증가하면서 해당 거리를 2번씩 이동하며,

마지막 이동에서는 N - 1 만큼 이동합니다.

토네이도의 방향을 2번씩 특정 거리만큼 움직이고 방향을 전환합니다. ←  ↓ → ↑

 

② 이동된 토네이도 위치와 방향에 따른 모래 처리

x → y에서 토네이도의 위치를 변경하고, 그에 따라 모래를 흩뿌립니다.

좌표 설정은 y 위치와 방향에 따른 비율입니다.

ex) wx[1][0], wy[1][0] percent[0]

      = 현재 토네이도의 방향은 "아래"이며, 비율 "1"에 해당하는 곳의 위치입니다.

- 격자를 벗어나는 경우에는 ans에 더합니다.

- 9가지 비율에 해당되는 곳에 모래를 보내주고 남은 모래는

  현재 방향의 다음위치에 보냅니다.

 

※ 디버깅 참고 코드

void printState() {
    printf("ans: %d\n", ans);
    printf("windy (%d , %d)\n", windy.x + 1, windy.y + 1);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            printf("%3d ", map[i][j]);
        }
        printf("\n");
    }
}

---

#include <stdio.h>
 
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { -1, 0, 1, 0 };
const int wx[4][9] =
{
    {-1, 1, -1, 1, -1, 1, -2, 2, 0}, // LEFT
    {-1, -1, 0, 0, 1, 1, 0, 0, 2}, // DOWN
    {-1, 1, -1, 1, -1, 1, -2, 2, 0 }, // RIGHT
    {1, 1, 0, 0, -1, -1, 0, 0, -2 }, // UP
};
 
const int wy[4][9] =
{
    {1, 1, 0, 0, -1, -1, 0, 0, -2}, // LEFT
    {-1, 1, -1, 1, -1, 1, -2, 2, 0}, // DOWN
    {-1, -1, 0, 0, 1, 1, 0, 0, 2}, // RIGHT
    {-1, 1, -1, 1, -1, 1, -2, 2, 0}, // UP
};
int percent[] = { 1, 1, 7, 7, 10, 10, 2, 2, 5 };
 
const int MAX_N = 500;
int N, map[MAX_N][MAX_N], ans;
 
struct Node {
    int x, y, dir;
}windy;
 
void sprinkSand() {
    int initVal = map[windy.x][windy.y];
    for (int i = 0; i < 9; ++i) {
        int x = windy.x + wx[windy.dir][i];
        int y = windy.y + wy[windy.dir][i];
 
        int sand = (initVal * percent[i]) / 100;
        map[windy.x][windy.y] -= sand;
        // 격자 밖을 벗어나는 경우
        if (x < 0 || y < 0 || x >= N || y >= N) {
            ans += sand;
            continue;
        }
        map[x][y] += sand;
    }
    
    // 비율만큼 보내고 남은 모래 처리
    int x = windy.x + dx[windy.dir];
    int y = windy.y + dy[windy.dir];
    if (x < 0 || y < 0 || x >= N || y >= N) {
        ans += map[windy.x][windy.y];
        map[windy.x][windy.y] = 0;
        return;
    }
    // 격자를 벗어나지 않는 경우
    map[x][y] += map[windy.x][windy.y];
    map[windy.x][windy.y] = 0;
}
 
void moveWindy(int len) {
    for (int i = 0; i < len; ++i) {
        windy.x += dx[windy.dir];
        windy.y += dy[windy.dir];
        sprinkSand();
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            scanf("%d", &map[i][j]);
        }
    }
 
    // 위치 방향
    windy = {N / 2, N / 2, 0};
    int len = 1;
    for (int i = 1; i < N; ++i) {
        for (int j = 1; j <= 2; ++j) {
            // 현재 바라보고 있는 방향으로 len만큼 이동
            moveWindy(len);
            // 방향 전환
            windy.dir = (windy.dir + 1) % 4;
        }
        len++;
    }
    
    // 마지막 이동 (제일 상단에 위치한 행)
    moveWindy(len - 1);
    printf("%d\n", ans);
}