문제
전형적인 시뮬레이션 문제다.
N X N 격자에서 (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다.
격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, 1번 행의 위에는 N번 행이 있고, 1번 열의 왼쪽에는 N번 열이, N번 열의 오른쪽에는 1번 열이 있다.
비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다. 구름은 칸 전체를 차지한다. 이제 구름에 이동을 M번 명령하려고 한다. i번째 이동 명령은 방향 di과 거리 si로 이루어져 있다. 방향은 총 8개의 방향이 있으며, 8개의 정수로 표현한다. 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.
한 사이클은 아래와 같다.
1. 모든 구름이 di 방향으로 si칸 이동한다.
2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
3. 구름이 모두 사라진다.
4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.
5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.
M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.
[풀이 코드]
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static int N, M, d, s;
static int[][] arr;
static int[] dr = {0, -1, -1, -1, 0, 1, 1, 1};
static int[] dc = {-1, -1, 0, 1, 1, 1, 0, -1};
static List<int[]> list;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
// 비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다.
list = new ArrayList<int[]>();
list.add(new int[]{N-1, 0});
list.add(new int[]{N-1, 1});
list.add(new int[]{N-2, 0});
list.add(new int[]{N-2, 1});
// M번 반복한다.
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
d = Integer.parseInt(st.nextToken())-1; // 방향
s = Integer.parseInt(st.nextToken()); // 거리
// 구름 이동 및 비 추가
move();
// 구름 생성
make();
}
// 물의 양의 합을 구한다.
System.out.println(result());
}
static int[] dr2 = {1, 1, -1, -1};
static int[] dc2 = {1, -1, 1, -1};
private static void move() {
for (int i = 0; i < list.size(); i++) {
int[] Idx = list.get(i);
for (int j = 0; j < s; j++) {
Idx[0] += dr[d];
Idx[1] += dc[d];
if(Idx[0] == -1) Idx[0] = N-1;
if(Idx[0] == N) Idx[0] = 0;
if(Idx[1] == -1) Idx[1] = N-1;
if(Idx[1] == N) Idx[1] = 0;
}
arr[Idx[0]][Idx[1]]+=1;
}
// 비 추가
for(int[] Idx : list) {
int sum = 0;
for (int d = 0; d < 4; d++) {
int nr = Idx[0] + dr2[d];
int nc = Idx[1] + dc2[d];
if(nr>=0 && nr<N && nc>=0 && nc<N && arr[nr][nc] > 0) sum++;
}
arr[Idx[0]][Idx[1]] += sum;
}
}
private static void make() {
List<String> temp = new ArrayList<String>();
for(int[] Idx : list) {
int r = Idx[0];
int c = Idx[1];
temp.add(r + ", " + c);
}
// 기존에 있던 구름 삭제
list.clear();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if(arr[i][j] >= 2 && !temp.contains(i + ", " + j)) {
arr[i][j] -= 2;
list.add(new int[]{i, j});
}
}
}
}
private static int result() {
int sum = 0;
for(int[] a : arr) {
for(int b : a) sum+=b;
}
return sum;
}
}이 문제를 해결하는데 1시간 넘게걸렸다..
하도 오답이 나오길래 처음부터 차근차근 봤는데 N X N 으로 입력을 받아야 하는데, 내가 N X M으로 입력을 받았다.. 너무 화가나는 걸
그래서 정답이 나올 줄 알았지만 또 오답이 나와버렸다.
이유를 찾아보니.. 구름 이동하고 나서, 해당 구름 위치에 +1을 해야 하는데, 나는 이 +1을 양쪽 대각선 방향에 물이 있는 갯수 만큼 더할 때, sum 값을 1로 하고 비의 양을 더했기 때문이다.
내 마음대로 풀지 말고,, 조건대로 풀자.!!
