[BOJ][삼성기출] 백준 20057번 - 마법사 상어와 토네이도 풀이

| |
백준 온라인 저지 20057번 - 마법사 상어와 토네이도 C++ 풀이 (삼성 SW 역량테스트 기출)


문제

마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다.

토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 토네이도의 이동이다.

1

토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다.

2

토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다. 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다. α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다. 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다. 위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다.

토네이도는 (1, 1)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.


입력

첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.


출력

격자의 밖으로 나간 모래의 양을 출력한다.


제한

  • 3 ≤ N ≤ 499
  • N은 홀수
  • 0 ≤ A[r][c] ≤ 1,000
  • 가운데 칸에 있는 모래의 양은 0


풀이

그동안 삼성에서 자주 출제되던 시뮬레이션 문제들과 사뭇 다른 느낌의 시뮬레이션 문제이다.

  • 상하좌우 움직임이 아닌 토네이도
  • 순차적인 시뮬레이션이 아닌 단순 수치 계산
  • 그래프 탐색 또는 완전탐색 개념의 부재

크게 이 3가지로 인해 꾸준히 삼성 기출을 풀어오던 사람이라면 조금 낯설게 느껴질 수 있다. 하지만 이러한 유형은 정확하고 효율적으로 구현하는 방법을 떠올리거나 비슷한 문제를 한 번이라도 풀어봤다면 그동안의 기출 문제보다 훨씬 짧은 시간 안에 해결할 수 있다.

이 문제에서 구현해야 할 핵심적인 요소는 다음 3가지이다.

  • 토네이도 이동
  • 모래양의 수치 계산
  • 이동 방향에 따른 흩날림 위치

우선 토네이도 이동 같은 경우엔 패턴을 찾아내야한다. 이동 방식을 잘 살펴보면 다음과 같은 특징을 찾아낼 수 있다.

  • 좌 하 우 상 반복이동
  • 이동하는 칸 수는 1 부터 시작하여 2번의 방향 회전마다 1 증가

필자는 이를 실수형을 이용한 2중 반복문으로 구현하였다. 자세한 것은 아래 전체 코드를 참조하기 바란다.

다음은 모래의 양 계산과 이동 방향에 따른 모래의 흩날림 위치 판단이다. 이를 쉽게 구현하기 위해선 상하좌우 4방향에 따른 기준점으로부터 모래의 흩날리는 모든 위치의 상대적인 좌표값을 미리 배열에 저장해두어야 한다. 그에 따른 모래의 비율 또한 앞서 작성한 배열의 상대적인 인덱스 값에 맞추어 배열을 만든 후 저장한다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
using namespace std;

int N;
int A[499][499];
const int dy[]={0,1,0,-1};
const int dx[]={-1,0,1,0};
const int ratio[9]={1,1,2,7,7,2,10,10,5};
const int blowY[4][10]={
    {-1,1,-2,-1,1,2,-1,1,0,0},
    {-1,-1,0,0,0,0,1,1,2,1},
    {-1,1,-2,-1,1,2,-1,1,0,0},
    {1,1,0,0,0,0,-1,-1,-2,-1}
};
const int blowX[4][10]={
    {1,1,0,0,0,0,-1,-1,-2,-1},
    {-1,1,-2,-1,1,2,-1,1,0,0},
    {-1,-1,0,0,0,0,1,1,2,1},
    {-1,1,-2,-1,1,2,-1,1,0,0}
};

bool inRange(int y, int x){
    return y>=0 && x>=0 && y<N && x<N;
}

// 모래의 흩날림 처리와 격자 밖 모래 반환
int blowSand(int y, int x, int dir){
    int ret=0, init=A[y][x];

    for(int i=0;i<10;i++){
        int sand;
        if(i!=9){
            sand=init*ratio[i]/100;
            A[y][x]-=sand;
        }
        else sand=A[y][x];

        int by=y+blowY[dir%4][i];
        int bx=x+blowX[dir%4][i];

        if(!inRange(by,bx)){
            ret+=sand;
            continue;
        }

        A[by][bx]+=sand;
    }

    A[y][x]=0;

    return ret;
}

int solve(){
    int ret=0, y=N/2, x=N/2, dir=0;

    // 토네이도 이동
    for(double i=1.0;i<=N;i+=0.5){
        for(int j=0;j<(int)i;j++){
            y+=dy[dir%4];
            x+=dx[dir%4];

            ret+=blowSand(y,x,dir);
        }
        dir++;
    }

    return ret;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

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

    cout<<solve();

    return 0;
}
0%