BOJ - 마법사 상어와 파이어볼 20056번 (JAVA)

❓ 문제 - 백준 마법사 상어와 파이어볼 20056번 - JAVA 풀이법

 

출처 

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

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

 

 

 

📝 문제해결법

1. 이 문제는 구현으로 풀었다.

• Node로 각 파이어볼의 ArrayList<Node> map의 2차원배열로 파이어볼의 위치를 관리한다.
• 각 파이어볼의 이동처리는 동시에 일어나므로 map_copy를 활용해서 파이어볼의 이동처리를 구현한다.
• 0번 행과 n-1행이 연결되어 있고, 0번 열이 n-1번 열과 연결되어 있으므로 하나의 파이어볼에 방향에 맞춰 속력s로 이동할 때 속력 s를 n으로 나눈 나머지로 nx, ny를 구한다. 만약 nx, ny가 0보다 작다면 n을 더해주고, nx, ny가 n보다 크거나 같다면 n을 빼준다. 원하는 방향으로 이동가능 하다.
• 만약에 한 곳에 여러 파이어볼이 이동하여 위치했다면 파이어볼의 질량, 속력, 방향을 주어진 식대로 구해주고, check1로 현재 위치에 존재하는 파이어볼이 모두 홀수인지 체크하고, check2로 현재 위치에 존재하는 파이어볼이 모두 짝수인지 체크해준다. 그리고 다 더한 질량의 합을 5로 나누었을 때 0보다 크지 않다면 소멸 처리, 아니면 해당 조건에 맞춰 4개의 파이어볼로 나누는 처리를 한다.

 

💻 소스코드

// BOJ - 마법사 상어와 파이어볼 (20056번)
// 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main_20056 {
	public static int n, m, k;

	public static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
	public static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
	public static ArrayList<Node>[][] map;
	
	public static class Node {
		int x;
		int y;
		int m;
		int d;
		int s;
		public Node(int x, int y, int m, int d, int s) {
			this.x = x;
			this.y = y;
			this.m = m;
			this.d = d;
			this.s = s;
		}
	}
	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());
		m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		map = new ArrayList[n][n];
		
		
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			if(map[x-1][y-1] == null) {
				map[x-1][y-1] = new ArrayList<Node>();
				map[x-1][y-1].add(new Node(x-1, y-1, m, d, s));
			} else {
				map[x-1][y-1].add(new Node(x-1, y-1, m, d, s));
			}
		}
		
		while(k-- > 0) {
			// 파이어볼 이동
			ArrayList<Node>[][] map_copy = new ArrayList[n][n];
			
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(map[i][j] == null) continue;
					for(int p=0;p<map[i][j].size();p++) {
						Node node = map[i][j].get(p);

						int nx = node.x + dx[node.d] * (node.s % n);
						int ny = node.y + dy[node.d] * (node.s % n);
		
						if(nx < 0) {
							nx = n - Math.abs(nx);
						} else if(nx >= n) {
							nx -= n;
						}
						if(ny < 0) {
							ny = n - Math.abs(ny);
						} else if(ny >= n) {
							ny -= n;
						}
			
						
						if(map_copy[nx][ny] == null) {
							map_copy[nx][ny] = new ArrayList<>();
						} 
						map_copy[nx][ny].add(new Node(nx, ny, node.m, node.d, node.s));
					}
				}
			}
			
			// 중복 처리
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(map_copy[i][j] == null || map_copy[i][j].size() == 1) {
						continue;
						
					}
					int sum_m = 0;
					int sum_s = 0;
					int size = map_copy[i][j].size();
					boolean check1 = true; // 홀수 체크
					boolean check2 = true; // 짝수 체크
					for(int p=0;p<map_copy[i][j].size();p++) {
						Node nd = map_copy[i][j].get(p);
						sum_m += nd.m;
						sum_s += nd.s;
						if(nd.d % 2 == 1) {
							check2 = false;
						} else {
							check1 = false;
						}
					}
					map_copy[i][j].clear();
					if(sum_m / 5 != 0) {

						for(int p=0;p<4;p++) {
							int dir = 0;
							if(check1 || check2) {
								dir = p*2;
							} else {
								dir = p*2+1;
							}
							map_copy[i][j].add(new Node(i, j, sum_m/5, dir, sum_s/size));
						}
					} 
				}
			}
			map = map_copy;
		}
		
		int ans = 0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(map[i][j] == null) continue;
				for(int p=0;p<map[i][j].size();p++) {
					ans += map[i][j].get(p).m;
				}
			}
		}
		System.out.println(ans);
	}

}