[BOJ][Java] 20056. 마법사 상어와 파이어볼

문제

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

 

문제 이해

• N×N 격자에서 파이어볼들이 K번 이동·합체·분리된다.
• 각 파이어볼: 위치 (r,c), 질량 m, 속력 s, 방향 d(0~7).
• 한 칸에 2개 이상 모이면 하나로 합친 뒤 4개로 분리
  • 새 질량 = ⌊(합 질량)/5⌋ (0이면 소멸)
  • 새 속력 = ⌊(합 속력)/개수⌋
  • 새 방향: 모두 짝/홀만 있었으면 {0,2,4,6}, 섞여 있으면 {1,3,5,7}

 

구현 흐름

1. 입력
   • fireBall 리스트에 모든 파이어볼 저장
   • map[r][c]에는 해당 칸에 존재하는 파이어볼 저장
2. K번 반복
   • 이동 move()
     • 모든 파이어볼을 방향·속력대로 이동
     • 이동 후 map에 삽입
   • 합체 후 4분리 divide(int r, int c)
     • map[i][j] >= 2인 칸만 divide(i, j) 수행
     • map 초기화
3. 출력
   • calcSum()로 남은 모든 파이어볼의 질량 합 출력

 

함수별 상세 기능

move(): 파이어볼 이동

방향 d로 s칸 이동. 격자의 범위, 음수를 고려하여 (r + dr[d] * (s % n) + n) % n로 처리

• s % n: s의 크기가 큰 경우를 고려하여 이동거리를 축소

 

divide(int r, int c): 합체 후 4분리

• map의 해당 칸을 한 번 순회하며, 질량 합 (m), 속력 합 (s), 파이어볼 개수 합 (cnt), 짝/홀 여부 (even/odd) 집계
• 합체된 파이어볼 제거: fireBall.remove(cur)
• 집계 후 map 초기화
• 새 질량, 속력, 방향 구하기
  • 새 질량: m /= 5 (0이면 소멸)
  • 새 속력: s /= cnt
  • 짝/홀 섞임 여부(odd && even)에 따라 방향 집합을 {0,2,4,6} 또는 {1,3,5,7}으로 4개 생성해 fireBall에 추가

 

calcSum(): 남은 질량 합산

• fireBall 리스트 순회하며 m을 누적해서 리턴

 

코드

import java.util.*;
import java.io.*;

public class Main {
	static class FireBall {
		int r, c, m, s, d;

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

	static int n;
	static ArrayList<FireBall>[][] map;
	static ArrayList<FireBall> fireBall;
	static int[] dr = { -1, -1, 0, 1, 1, 1, 0, -1 };
	static int[] dc = { 0, 1, 1, 1, 0, -1, -1, -1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		map = new ArrayList[n][n];
		fireBall = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map[i][j] = new ArrayList<>();
			}
		}

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken()) - 1;
			int c = Integer.parseInt(st.nextToken()) - 1;
			fireBall.add(new FireBall(r, c, Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),
					Integer.parseInt(st.nextToken())));
		} // 입력 끝

		while (k-- > 0) { // 명령
			move();

			// 파이어볼 분리 & map 초기화
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (map[i][j].size() < 2) {
						map[i][j].clear();
						continue;
					}
					divide(i, j);
				}
			}
		}

		System.out.println(calcSum());
	}

	static void move() { // 파이어볼 이동
		for (FireBall f : fireBall) {
			f.r = (f.r + n + dr[f.d] * (f.s % n)) % n;
			f.c = (f.c + n + dc[f.d] * (f.s % n)) % n;
			map[f.r][f.c].add(f);
		}
	}

	static void divide(int r, int c) { // 파이어볼 분리
		int m = 0, s = 0, cnt = map[r][c].size();
		boolean odd = false, even = false;

		for (FireBall cur : map[r][c]) {
			m += cur.m;
			s += cur.s;
			if (cur.d % 2 == 0)
				even = true;
			else
				odd = true;

			fireBall.remove(cur);
		}
		map[r][c].clear();

		m /= 5;
		if (m == 0) { // 소멸
			return;
		}

		s /= cnt;

		if (odd && even) {
			for (int i = 1; i < 8; i += 2) {
				fireBall.add(new FireBall(r, c, m, s, i));
			}
		} else {
			for (int i = 0; i < 8; i += 2) {
				fireBall.add(new FireBall(r, c, m, s, i));
			}
		}
	}

	static int calcSum() { // 질량 합
		int ans = 0;

		for (FireBall f : fireBall) {
			ans += f.m;
		}

		return ans;
	}
}