[백준] 20056번 마법사 상어와 파이어볼 (java, 구현, bfs)

www.acmicpc.net/problem/20056

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

bfs로 뭐든 되는구나 싶었다 

1번이랑 n번이 연결된다는게 뭔가 싶었는데 범위를 넘어가면 그만큼 빼서 다시 안의 범위로 들어오게 해야된다

 

그 다음에는 파이어 볼 개수만큼 큐에 집어넣고 그 길이만큼만 bfs로 돌린 후 다시 새로 만든 파이어볼을 큐에 넣고 

k번 돌리면 된다. 

 

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Fire{
	int r,c,m,s,d;

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

	@Override
	public String toString() {
		return "Fire [r=" + r + ", c=" + c + ", m=" + m + ", s=" + s + ", d=" + d + "]";
	}

	
}

public class Main {

	static int n,m,k;
	static int[]xpos= {0,1,1,1,0,-1,-1,-1};
	static int[]ypos= {-1,-1,0,1,1,1,0,-1};
	static ArrayList<Fire>[][] map;
	static Queue<Fire> q=new LinkedList<Fire>();
	public static void main(String[] args) {

		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		k=sc.nextInt();
		map=new ArrayList[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				map[i][j]=new ArrayList<>();
			}
		}
		for (int i = 0; i < m; i++) {
			//r,c,m,s,d
			q.add(new Fire(sc.nextInt()-1,sc.nextInt()-1,sc.nextInt(),sc.nextInt(),sc.nextInt()));
		}

//		r,c,m,s,d
		for (int t = 0; t < k; t++) {//k번 파이어볼이동
				int len=q.size();
					//모든 파이어 볼 이동
				for (int move = 0; move < len; move++) {
						Fire cur=q.poll();
						int y=cur.r;
						int x=cur.c;
						int w=cur.m;
						int s=cur.s;
						int d=cur.d;
						int yy=y+ypos[d]*(s%n);
						int xx=x+xpos[d]*(s%n);
						yy=(yy+n)%n;
						xx=(xx+n)%n;
						map[yy][xx].add(new Fire(yy,xx,w,s,d));
						
					}
					
//					// 이동 후 합치고 분할
					for (int y = 0; y < n; y++) {
						for (int x = 0; x < n; x++) {
							if(map[y][x].size()==0)continue;
							if(map[y][x].size()==1) {//1개인 칸은 그냥 큐에 넣는다.
								q.add(map[y][x].get(0));
								continue;
							}
							//2개 이상인 칸 
							int weight=0;
							int fast=0;
							int odd=0;
							int even=0;
							for (int j = 0; j < map[y][x].size(); j++) {
								weight+=map[y][x].get(j).m;
								fast+=map[y][x].get(j).s;
								if((map[y][x].get(j).d)%2==0) {
									even++;
								}else {
									odd++;
								}
							}
							weight/=5;
							fast/=map[y][x].size();
							//질량이 0인 곳은 소멸함
							if(weight==0)continue;
							if(odd==0 || even==0) {
								q.add(new Fire(y,x,weight,fast,0));
								q.add(new Fire(y,x,weight,fast,2));
								q.add(new Fire(y,x,weight,fast,4));
								q.add(new Fire(y,x,weight,fast,6));
							}else {
								q.add(new Fire(y,x,weight,fast,1));
								q.add(new Fire(y,x,weight,fast,3));
								q.add(new Fire(y,x,weight,fast,5));
								q.add(new Fire(y,x,weight,fast,7));
							}
						}
					}
					//map초기화
					for (int y = 0; y < n; y++) {
						for (int x = 0; x < n; x++) {
							map[y][x]=new ArrayList<>();
						}
					}
					
				}
				

		int answer=0;
		int len=q.size();
		for (int i = 0; i < len; i++) {
			answer+=q.poll().m;
		}
		System.out.println(answer);
	}
}