백준 20056 : 마법사 상어와 파이어볼

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

20056번: 마법사 상어와 파이어볼

[ 문제풀이 ]

주어진 지문을 토대로 총 3단계 과정으로 세분화할 수 있다. 좌표에 여러 개의 파이어볼이 존재할 수 있기 때문에 삭제, 삽입이 빠른 LinkedList를 이용하여 Map을 구현하였다.

​1. 모든 파이어볼이 자신의 방향 d로 속력 s 칸만큼 이동시킨다. 이동할 좌표를 구할 때 모듈러 연산을 활용하면 빠르게 구할 수 있다. 양수일 경우 단순히 모듈러 연산을 하면 되지만, 음수인 경우 양수화를 시키기 위해 N의 값을 더해준 후 %N을 진행한다.

​2. 이동한 후 각 좌표의 파이어볼 개수를 업데이트한다. Map의 개수를 1번에서 업데이트하기 때문에 업데이트 전후의 Map의 개수가 다르다. 이를 해결하기 위해 별도의 2차원 배열을 하나 만들어 업데이트 전후의 파이어볼 개수를 관리한다.

​3. 2개 이상 파이어볼이 모여있는 경우 주어진 조건에 따라 합친 후 분할한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
	
	static int N, M, K;
	static LinkedList<FireBall>[][] map;
	static int[][] fireBallCnt;
	static int[][] dir = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};
	
	static class FireBall {
		int m, s, d;

		public FireBall(int m, int s, int d) {
			this.m = m;
			this.s = s;
			this.d = d;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());

		map = new LinkedList[N][N];
		//파이어볼을 업데이트하는 과정에서 파이어볼의 갯수의 오류를 없애기 위해
		fireBallCnt = new int[N][N];
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				map[i][j] = new LinkedList<>();
			}
		}

		//편하게 구현하기 위해 y, x 좌푯값을 -1해서 받음
		for (int i = 0; i < M; ++i) {
			st = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(st.nextToken()) - 1;
			int x = Integer.parseInt(st.nextToken()) - 1;
			int m = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());

			map[y][x].add(new FireBall(m, s, d));
			fireBallCnt[y][x]++;
		}

		while (K-- > 0) {
			//1. 모든 파이버볼이 자신의 방향 d로 속력 s칸 만큼 이동
			moveTheFireBall();
			//2. 이동한 후 파이어볼의 갯수 업데이트
			updateTheFireBallCnt();
			//3. 2개 이상 파이어볼이 모여있으면 합친 후 분할
			updateTheFireBall();
		}
		bw.write(sum() + "\n");
		bw.flush(); br.close(); bw.close();
	}

	public static void moveTheFireBall() {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				for (int k = 0; k < fireBallCnt[i][j]; ++k) {
					FireBall fb = map[i][j].poll();
					
					//파이어볼의 좌표를 모듈러 연산을 통해 빠르게 구함 
					int y = (i + dir[fb.d][0] * fb.s) % N;
					int x = (j + dir[fb.d][1] * fb.s) % N;
					
					//좌표가 음수인 경우 양수화 시킴
					if (y < 0) y = (N + y) % N;
					if (x < 0) x = (N + x) % N;
					
					map[y][x].add(fb);
				}
			}
		}
	}

	public static void updateTheFireBallCnt() {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				fireBallCnt[i][j] = map[i][j].size();
			}
		}
	}

	public static void updateTheFireBall() {
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (fireBallCnt[i][j] >= 2) {
					int totalDir = 0;
					int totalWeight = 0;
					int totalSpeed = 0;

					for (int k = 0; k < fireBallCnt[i][j]; ++k) {
						FireBall fb = map[i][j].poll();

						totalDir += fb.d % 2 == 0 ? 1 : -1;
						totalWeight += fb.m;
						totalSpeed += fb.s;
					}

					totalWeight /= 5;
					totalSpeed /= fireBallCnt[i][j];

					//질량이 0이면 파이어볼은 소멸됨
					if (totalWeight == 0) {
						fireBallCnt[i][j] = 0;
						continue;
					}

					//파이어볼의 방향이 모드 홀수이거나 짝수이면
					if (fireBallCnt[i][j] * 1 == totalDir || fireBallCnt[i][j] * -1 == totalDir) {
						for (int k = 0; k < 4; ++k) {
							map[i][j].add(new FireBall(totalWeight, totalSpeed, k * 2));
						}
					} else {
						for (int k = 0; k < 4; ++k) {
							map[i][j].add(new FireBall(totalWeight, totalSpeed, k * 2 + 1));
						}
					}

					fireBallCnt[i][j] = 4;
				}
			}
		}
	}

	public static int sum() {
		int answer = 0;
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (fireBallCnt[i][j] > 0) {
					while (!map[i][j].isEmpty()) {
						answer += map[i][j].poll().m;
					}
				}
			}
		}
		return answer;
	}
}