CodeDrive

문제:

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

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

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

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

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

입력:

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

출력:

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

풀이방법:

 이 문제의 핵심은 회오리 모양으로 토네이도가 이동하는 것을 구현, 토네이도가 이동함에 따라 모래가 흩날리는 것을 구현해야 한다.

우선 회오리 모양으로 이동하는 것은 다음과 같은 규칙이 있다.

1) 방향은 좌, 하, 우, 상 을 반복하며 진행된다.

  - 따라서 dx, dy를 +1할 때마다 방향이 좌, 하, 우, 상으로 바뀌게 설정한다.

2) 좌, 하, 우, 상으로 이동할 때 거리는 1, 1, 2, 2, 3, 3, 4, 4, .... 와 같이 매 짝수 인덱스마다 증가하게 된다.

  - 다만 맨 마지막은 N-1, N-1, N, N, N 과 같이 N이 3번 반복되며 끝난다.

따라서 1), 2)의 조건을 만족하며 토네이도를 이동시키고, 토네이도가 0,0에 도달하면 이동을 종료하도록 한다. (소멸)

 모래가 흩날리는 것은 spread라는 배열을 만들어서 해결한다. 모래가 흩날리는 것은 좌, 하, 우, 상에 따라 흩날리는 위치가 다르기 때문에 방향 인덱스에 따라 모래의 이동 인덱스를 정리해둔다. 그리고 해당 인덱스에 따라 모래가 이동할 양인 ratio를 설정하도록 한다. 이 때, a의 경우에는 ratio를 0으로 설정한 뒤 따로 설정하도록 한다. 

 global 변수 answer를 설정하고, 범위 밖으로 나가는 모래는 다 answer에 더하고, 나머지는 지도에 계속 누적시키도록 한다.

이 두 기능을 계속해서 반복했을 때, 최종 answer를 출력한다.

문제링크:

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