[ 알고리즘 ] 코딩 - 백준 20056 - 마법사 상어와 파이어볼.java

---

문제 링크

www.acmicpc.net/problem/20056

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

---

문제개요

BOJ 20056 - (자바) 마법사 상어와 파이어볼 - 시뮬레이션 / 구현 / 2차원 리스트 배열

마법사 상어가 크기가 N×N인 격자에 파이어볼 M개를 발사했다. 가장 처음에 파이어볼은 각자 위치에서 이동을 대기하고 있다. i번 파이어볼의 위치는 (ri, ci), 질량은 mi이고, 방향은 di, 속력은 si이다. 위치 (r, c)는 r행 c열을 의미한다.

격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.

파이어볼의 방향은 어떤 칸과 인접한 8개의 칸의 방향을 의미하며, 정수로는 다음과 같다.

파이어볼 방향 인덱스

마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음이 일들이 일어난다.

1. 모든 파이어볼이 자신의 방향 di로 속력 si칸 만큼 이동한다.
   • 이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수도 있다.
2. 이동이 모두 끝난 뒤, 2개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어난다.
   1. 같은 칸에 있는 파이어볼은 모두 하나로 합쳐진다.
   2. 파이어볼은 4개의 파이어볼로 나누어진다.
   3. 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.
      1. 질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다.
      2. 속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
      3. 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.
   4. 질량이 0인 파이어볼은 소멸되어 없어진다.

마법사 상어가 이동을 K번 명령한 후, 남아있는 파이어볼 질량의 합을 구해보자.

ri, ci, mi, si, di 순으로 입력이 주어진다.

---

로직

Step 01. 파이어볼의 정보를 담을 class 하나와 지도의 y,x 좌표에 대응해서 저장할 2차원 리스트 배열을 하나 만든 후 초기화 한 후, 입력을 받아 현재 파이어볼을 담는다. 

Step 02. 파이어볼을 이동시킨다. 이때 원래 파이어볼의 정보가 담긴 2차원 리스트배열(fireballs)을 토대로 이동을 시켜준다. 새로운 2차원 리스트 배열을 생성(sum_balls)해서 이동을 한 후 원래의 fireballs 배열에 옮겨주자. 이때 범위를 벗어나면 사라지는 것이 아닌 반대의 방향으로 나오는 것에 유의하자! 또, 스피드 최대치가 1000으로 지도보다 훨씬 큰 값이 들어오는 경우도 있으므로 speed%n 해주는 것을 잊지말자.

Step 03. 겹쳐진 파이어볼을 제거한 후 4개의 파이어볼로 분리한다. Step 02에서 변경된 fireballs 배열을 이용해서 합쳐진 파이어볼이 있는지 판단. 합쳐진 파이어볼이 있다면 분리해주는데 이때 모두 짝수 방향이거나 모두 홀수 방향인 경우를 잘 판단해서 분리. 합쳐진 파이어볼의 방향중 하나라도 짝수면 홀수를 false해주고 하나라도 홀수면 짝수를 false해주면 된다.

Step 04. Step 02-Step03을 K번 반복한 후 남은 파이어볼의 질량의 합을 구하면 정답!  

다 풀고나서 보면 진짜 별거 아닌데 2차원 리스트 배열을 떠올리는데 시간이 조금 오래걸렸다. 하나의 리스트로 구현했다가 시간이 초과되고, 방향전환하다가 이상한데 접근하고.. 나한테는 참 어려웠다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static class Fireball { // 파이어볼 정보
		int d, s, m;

		public Fireball() {
			super();
		}

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

		@Override
		public String toString() {
			return " d: " + this.d + " s: " + this.s + " m: " + this.m;
		}
	}

	private static int WEIGHT;
	private static int[] dy = { -1, -1, 0, 1, 1, 1, 0, -1 };
	private static int[] dx = { 0, 1, 1, 1, 0, -1, -1, -1 };

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

		int N = Integer.parseInt(stt.nextToken());
		int M = Integer.parseInt(stt.nextToken());
		int K = Integer.parseInt(stt.nextToken());

		List<Fireball>[][] fireballs = new ArrayList[N + 1][N + 1];

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				fireballs[i][j] = new ArrayList<Fireball>();
			}
		}

		// Step 01. 모든 파이어볼의 정보를 2차원 리스트 배열로 만들어 저장.
		// fireballs[y][x] 는 y,x좌표를 뜻한다.
		for (int i = 0; i < M; i++) {
			stt = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(stt.nextToken());
			int x = Integer.parseInt(stt.nextToken());
			int m = Integer.parseInt(stt.nextToken());
			int s = Integer.parseInt(stt.nextToken());
			int d = Integer.parseInt(stt.nextToken());
			fireballs[y][x].add(new Fireball(m, s, d));
		}

		// 이동 및 분리
		fireballs = process(fireballs, N, K);
		// Step 04. 모든 이동을 마친 후 남은 파이어볼의 질량 합산
		sumWeight(fireballs, N);

		System.out.println(WEIGHT);
	}

	private static void sumWeight(List<Fireball>[][] fireballs, int n) {
		// 모든 질량 합하기.
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (fireballs[i][j].size() > 0) {
					for (Fireball cur_ball : fireballs[i][j]) {
						WEIGHT += cur_ball.m;
					}
				}
			}
		}
	}

	private static List<Fireball>[][] process(List<Fireball>[][] fireballs, int n, int k) {
		int move_cnt = 0;
		while (move_cnt < k) {
			move_cnt++;

			// Step 02. 파이어볼을 이동시키자. 이동 하고난 다음의 2차원 리스트 배열을 넘겨 받아 
			// Step03으로 간다.
			fireballs = moveFireballs(fireballs, n);

			// Step 03. 겹친 파이어볼을 분리시키자.
			checkOverlapBalls(fireballs, n);
		}
		// 모든 과정이 끝난 다음의 2차원 리스트 배열을 반환
		return fireballs;
	} // process 종료

	private static List<Fireball>[][] moveFireballs(List<Fireball>[][] fireballs, int n) {
		List<Fireball>[][] sum_balls = new LinkedList[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				sum_balls[i][j] = new LinkedList<Fireball>();
			}
		}
		// 모든 파이어볼 이동
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (fireballs[i][j].size() > 0) {
					for (Fireball cur_ball : fireballs[i][j]) {
						int cur_d = cur_ball.d;
						int cur_s = cur_ball.s % (n);
						int cur_m = cur_ball.m;

						// 현재 위치에서 지정된 방향으로 S칸 만큼 이동
						int next_y = i + dy[cur_d] * cur_s;
						int next_x = j + dx[cur_d] * cur_s;

						// 범위를 벗어난 경우. 반대 방향으로 나온다.
						next_x = next_x > n ? next_x - n : 
						next_x < 1 ? next_x + n : next_x;
                        
						next_y = next_y > n ? next_y - n : 
						next_y < 1 ? next_y + n : next_y;

						// 해당 좌표에 파이어볼을 위치시킨다.
						sum_balls[next_y][next_x].add(new Fireball(cur_m, cur_ball.s, cur_d));
					}
				}
			}
		} // 이동 끝
		return sum_balls;
	}

	private static void checkOverlapBalls(List<Fireball>[][] fireballs, int n) {
		// 겹친 파이어볼 있는지 체크
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				// 겹친 파이어볼이 있는 경우!
				if (fireballs[i][j].size() > 1) {
					int sum_m = 0;
					int sum_s = 0;
					boolean isEven = true, isOdd = true; // 짝수 홀수 판단.

					for (Fireball cur_ball : fireballs[i][j]) {
						sum_m += cur_ball.m;
						sum_s += cur_ball.s;
						if (cur_ball.d % 2 == 0)
							isOdd = false;
						else
							isEven = false;
					}

					sum_s /= fireballs[i][j].size();
					sum_m /= 5;
					// 일단 겹친 파이어볼 모두 제거한다.
					fireballs[i][j].clear();

					// 합한 질량이 0이면 다음에 겹치는거 탐색
					if (sum_m == 0)
						continue;

					if (isEven || isOdd) { // 모두 짝/홀 방향이었다.
						int[] dir = { 0, 2, 4, 6 };
						for (int d = 0; d < 4; d++) {
							fireballs[i][j].add(new Fireball(sum_m, sum_s, dir[d]));
						}
					} else { // 다른 방향이 하나라도 있었다.
						int[] dir = { 1, 3, 5, 7 };
						for (int d = 0; d < 4; d++) {
							fireballs[i][j].add(new Fireball(sum_m, sum_s, dir[d]));
						}
					}
				}
			}
		} // 파이어볼 체크 종료
	}
}