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

최근에 나온 삼성 역량 테스트 시뮬레이션 문제이다.

 

문제 풀이 순서

1. 모든 파이어볼을 담을 queue를 이용해서 이동시킨다.
2. 한자리에 모여 있는 수가 2개일 경우 결합과 분해가 일어나고 1개일 경우 바로 queue에 다시 넣어준다.
3. K번을 수행하고 난 뒤 queue에 있는 무게를 더하면 된다. 

파이어볼의 상태를 나타내기 위해 fire이라는 클래스를 선언했다.

또한 이동 후의 상태를 저장한 move 클래스를 선언했다.

 

파이어 볼을 이동하면서 주의해야 할 점은

 

이 과정을 해줘야 한다는 것이다.

 

파이어볼을 이동할 때 몇 개가 겹치는 지를 알아야 하기 때문에 ArrayList <integer> map [][]을 사용

 

또한 그것의 상태를 저장하기 위한 ArrayList<move> al를 사용

 

다음 그림과 같이 처리를 한다.

 

그리고 모든 맵의 Arraylist를 돌면서 개수가 1인 경우는 그냥 queue에 넣어주고 2보다 크거나 같은 경우 하나씩 확인하면서 계산을 통해 Queue에 넣어주면 된다.

각 칸의 짝수 홀수인지를 판단 

 

그렇게 어렵지는 않은 문제이지만 생각을 필요로 하는 것 같다.

 

전체 코드

 

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

public class Main {
	public static class fire {
		int x;
		int y;
		int m;
		int d;
		int s;

		public fire(int x, int y, int m, int s, int d) {
			super();
			this.x = x;
			this.y = y;
			this.m = m;
			this.s = s;
			this.d = d;

		}
	}

	public static class move {
		int m;
		int s;
		int d;

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

	static Queue<fire> q;
	static ArrayList<Integer> map[][];
	static long sum;
	static int n, m, k,
			dir[][] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 } };

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		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());
		q = new LinkedList<fire>();
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken()) - 1;
			int y = Integer.parseInt(st.nextToken()) - 1;
			int m = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			q.add(new fire(x, y, m, v, d));
		}
		start();
		System.out.println(sum);
	}

	private static void start() {
		// TODO Auto-generated method stub
		for (int i = 0; i < k; i++) {
			ArrayList<move> al = new ArrayList<move>();
			map = new ArrayList[n][n];
			for (int j = 0; j < n; j++) {
				for (int h = 0; h < n; h++) {
					map[j][h] = new ArrayList<Integer>();
				}
			} // 초기화
			while (!q.isEmpty()) {
				fire next = q.remove();
				int x1 = next.x + dir[next.d][0] * next.s;
				int y1 = next.y + dir[next.d][1] * next.s;
				if (x1 < 0) {
					x1 = (n - (Math.abs(x1) % n));
				}
				if (x1 >= n) {
					x1 = (x1 % n);
				}
				if (y1 < 0) {
					y1 = (n - (Math.abs(y1) % n));
				}
				if (y1 >= n) {
					y1 = (y1 % n);
				}
				map[x1][y1].add(al.size());
				al.add(new move(next.m, next.s, next.d));
			}
			for (int j = 0; j < n; j++) {
				for (int h = 0; h < n; h++) {
					if (map[j][h].size() >= 2) {
						int m0 = 0;
						int v0 = 0;
						int Wkr = 0;
						int ghf = 0;
						for (int w = 0; w < map[j][h].size(); w++) {
							int next = map[j][h].get(w);
							move ne = al.get(next);
							m0 += ne.m;
							v0 += ne.s;
							if (ne.d % 2 == 0) {
								Wkr++;
							} else {
								ghf++;
							}
						}
						m0 = m0 / 5;
						v0 = v0 / map[j][h].size();
						if (m0 == 0) {
							continue;
						}
						if (Wkr > 0 && ghf > 0) {
							for (int w = 1; w <= 7; w += 2) {
								q.add(new fire(j, h, m0, v0, w));
							}
						} else {
							for (int w = 0; w <= 6; w += 2) {
								q.add(new fire(j, h, m0, v0, w));
							}

						}

					} else if (map[j][h].size() == 1) {
						int next = map[j][h].get(0);
						move ne = al.get(next);
						q.add(new fire(j, h, ne.m, ne.s, ne.d));
					}
				}
			}
		}
		while (!q.isEmpty()) {
			sum += q.remove().m;
		}

	}

}