[Algorithm] 백준. 20056 마법사 상어와 파이어볼

2020년 하반기 삼성 코딩테스트 기출문제인 마법사 상어와 파이어볼.

www.acmicpc.net/problem/20056

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

당시 코딩테스트를 응시했을때 10개의 테스트 케이스 중 2~3개가 맞지않아서 풀지 못한채로 마무리해서 아쉬웠던 기억이 난다. 다시 문제를 풀어보니 파이어볼 여러개가 합쳐지고, 나누어지는 과정에서 제자리에서 나눠지도록 구현했어야 했는데, 나눠진 파이어볼을 처음부터 속도만큼 이동하도록 구현한 것이 화근이였던 것 같다. 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M, K;
	static int dy[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
	static int dx[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
	static Fire map[][];
	static int number[][];
	static int bal[][];
	static Queue<Fire> q;

	public static class Fire {
		int y, x, m, s, d;

		public Fire(int y, int x, int m, int s, int d) {
			this.y = y;
			this.x = x;
			this.m = m;
			this.s = s;
			this.d = d;
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken()); // K초 후 상태
		q = new LinkedList<>();
		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());
			q.add(new Fire(y, x, m, s, d));
		}
		for (int i = 0; i < K; i++) {
			map = new Fire[N][N];
			number = new int[N][N];
			bal = new int[N][N];// 0: 상하좌우로만 모인경우 , 1: 대각선으로만, 2: 섞인경우
			bfs();
			fireAddQueue();
		}
		int res = 0;
		while (!q.isEmpty()) {
			Fire pp = q.poll();
			res += pp.m;
		}
		System.out.println(res);
	}

	private static void fireAddQueue() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (number[i][j] == 0) {
					continue;
				} else if (number[i][j] == 1) {
					q.add(map[i][j]);
				} else if (number[i][j] > 1) {
					int m = map[i][j].m / 5;
					int s = map[i][j].s / number[i][j];
					if (m == 0)
						continue;
					for (int d = 0; d < 8; d += 2) {
						if (bal[i][j] == 2) { // 방향 섞인경우
							q.add(new Fire(i, j, m, s, d + 1));
						} else {// 상하좌우 or 대각선으로만 이뤄진 경우
							q.add(new Fire(i, j, m, s, d));
						}
					}
				}
			}
		}
	}

	private static void bfs() {
		while (!q.isEmpty()) {
			int size = q.size();
			for (int i = 0; i < size; i++) {
				Fire p = q.poll();
				int y = p.y + dy[p.d] * p.s;
				int x = p.x + dx[p.d] * p.s;
				y = abs(y);
				x = abs(x);
				if (number[y][x] == 0) {
					number[y][x]++;
					bal[y][x] = p.d % 2;
					map[y][x] = new Fire(y, x, p.m, p.s, p.d);
				} else {// 여러개 파이어볼 모이는 경우
					number[y][x]++;
					map[y][x].m += p.m;
					map[y][x].s += p.s;
					if (bal[y][x] < 2) {
						if (bal[y][x] == p.d % 2) {
							continue;
						} else {
							bal[y][x] = 2;
						}
					}
				}
			}
		}
	}

	private static int abs(int number) {
		if (number >= N) {// 범위초과시
			number = number % N;
		} else if (number < 0) {// 음수 범위초과시
			number = (N - Math.abs(number) % N) % N;
		}
		return number;
	}

}

 

질량이 0인 경우는 제외(속도가 0인 것은 포함)

음수범위초과 로직이 깔끔하지 못한 것 같아 더 좋은 방식을 찾아봐야 할 것 같다.