[백준] 20057번: 마법사 상어와 토네이도 - C++

문제

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

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

 

문제 설명

토네이도는 격자의 가운데부터 이동이 시작된다.

좌표의 시작이 (1, 1)이라고 할 때, 격자의 가운데 칸의 좌표는 (N/2+1, N/2+1)이다.

 

격자의 가운데 칸의 좌표를 x라고 할때, x는 화살표를 따라서 움직인다.

N = 7일때, 1 1 2 2 3 3 4 4 5 5 6 6 7 순서로 왼 - 아래 - 오른쪽 - 위로 움직인다.

 

x가 토네이도의 중심일 때, x가 y방향으로 움직이면 다음과 같이 비율은 정해진다.

1) 왼쪽으로 이동

		2%
	10%	7%	1%
5%	a	y	x
	10%	7%	1%
		2%

2) 아래로 이동

	1%	x	1%
2%	7%	y	7%	2%
	10%	a	10%
		5%

 

3) 오른쪽으로 이동

		2%
	1%	7%	10%
	x	y	a	5%
	1%	7%	10%
		2%

4) 위로 이동

		5%
	10%	a	10%
2%	7%	y	7%	2%
	1%	x	1%

 

왼, 아래, 오, 위 방향은 dir 배열에 저장해 놓았다.

rate에는 곱해져야하는 비율을, idx에는 왼, 아래, 오, 위 방향 순서대로 비율과 곱해져야하는 칸의 위치를 저장해주었다.

//왼, 아래, 오, 위
int dir[4][2]= {{0,-1},{1,0},{0,1},{-1,0}};
double rate[9] = {0.01, 0.01, 0.02, 0.02, 0.07, 0.07, 0.1, 0.1, 0.05};
int idx[4][10][2] = {{{-1,0},{1,0}, {-2,-1}, {2,-1}, {-1,-1}, {1,-1},{-1,-2}, {1,-2},{0,-3},{0,-2}},
    {{0,-1},{0,1}, {1,-2},{1,2},{1,-1},{1,1},{2,-1},{2,1}, {3,0}, {2,0}},
    {{-1,0},{1,0},{-2,1},{2,1},{-1,1},{1,1},{-1,2},{1,2},{0,3}, {0,2}},
    {{0,-1},{0,1},{-1,-2},{-1,2},{-1,-1},{-1,1},{-2,-1},{-2,1},{-3,0}, {-2,0}}
};

문제에 대한 이해를 돕기 위해

예제 2에 대한 과정을 출력해 보았다.

예제 2

1칸 왼쪽으로 이동

1칸 아래로 이동

 

2칸 오른쪽으로 이동

 

2칸 위로 이동

 

3칸 왼쪽으로 이동

3칸 아래로 이동

4칸 오른쪽으로 이동

4칸 위로 이동

5칸 왼쪽으로 이동

전체 코드

#include <iostream>
#include <vector>

using namespace std;

// 20057번

int A[500][500];

//왼, 아래, 오, 위
int dir[4][2]= {{0,-1},{1,0},{0,1},{-1,0}};
double rate[9] = {0.01, 0.01, 0.02, 0.02, 0.07, 0.07, 0.1, 0.1, 0.05};
int idx[4][10][2] = {{{-1,0},{1,0}, {-2,-1}, {2,-1}, {-1,-1}, {1,-1},{-1,-2}, {1,-2},{0,-3},{0,-2}},
    {{0,-1},{0,1}, {1,-2},{1,2},{1,-1},{1,1},{2,-1},{2,1}, {3,0}, {2,0}},
    {{-1,0},{1,0},{-2,1},{2,1},{-1,1},{1,1},{-1,2},{1,2},{0,3}, {0,2}},
    {{0,-1},{0,1},{-1,-2},{-1,2},{-1,-1},{-1,1},{-2,-1},{-2,1},{-3,0}, {-2,0}}
};

int main(int argc, const char * argv[])
{
    int N;
    cin >> N;
    int result = 0;
    
    for(int i = 1; i<=N; i++)
    {
        for(int j = 1; j<=N; j++)
        {
            cin >> A[i][j];
        }
    }
    
    // r, c는 x의 좌표
    int r = N/2+1;
    int c = N/2+1;
    int y = 0;
    
    // 112233445 -> 9번
    for(int i = 1; i<=2*N-1 ; i++)
    {
    	//fin은 몇 칸 이동할 것인지
        int fin = (i+1)/2;
        if(i == 2*N) fin -= 1;
       
        
        //방향 설정: 왼 아 오 위
        int dr = dir[(i-1)%4][0];
        int dc = dir[(i-1)%4][1];
        
        for(int j = 1; j<=fin;j++)
        {
            y = A[r+dr][c+dc];
            A[r+dr][c+dc] = 0; //y의 모래를 이동시키는 것이므로, y자리는 0으로 채워준다. 
            
            int alpha = y;
            
            //비율
            for(int k = 0; k<10; k++)
            {
                if((r+idx[(i-1)%4][k][0] > 0 && r+idx[(i-1)%4][k][0] <= N) &&
                   (c+idx[(i-1)%4][k][1] > 0 && c+idx[(i-1)%4][k][1] <= N))
                {
                    A[r+idx[(i-1)%4][k][0]][c+idx[(i-1)%4][k][1]] +=  (int)((double)y * rate[k]);
                }
                else	// 격자 밖으로 나간 경우는 result에 누적해서 더해준다.
                {
                    result += (int)((double)y * rate[k]);
                }
                alpha -= (int)((double)y * rate[k]);	//이동시킨 모래는 알파에서 빼준다.
                
            }
            
            // 알파위치의 값을 계산
            if((r+idx[(i-1)%4][9][0] > 0 && r+idx[(i-1)%4][9][0] <= N) &&
               (c+idx[(i-1)%4][9][1] > 0 && c+idx[(i-1)%4][9][1] <= N))
            {
                A[r+idx[(i-1)%4][9][0]][c+idx[(i-1)%4][9][1]] += alpha;
            }
            else
                result += alpha;
            
            //이동
            r += dr;
            c += dc;
        }
    }
    
    cout << result << endl;
}

 

 

처음에 문제를 이해하는 데에 시간이 상당히 많이 걸렸다. 시뮬레이션 문제는 처음 접해서 그런지 어렵게 느껴졌다.

경우를 나누고 풀다보니 조금씩 해결할 수 있었고, 출력을 통해서 어느부분이 잘못되었는지 확인하였다.