BOJ_20056_마법사 상어와 파이어볼

1

구분: 구현, 시뮬레이션
언어: Java
전략:

• 
  큐에 있는 것들은 이동을 할 공들
• ArrayList[][]에 있을 것들 - 공이 이동하고, 여러 개의 공이 있을 수 있기 때문에 ArrayList 2차원 배열을 생성
• 이동 시키기 - 모듈러 연산을 이용해서 간단하게 구할 수 있다.
• 좌표, 질량, 속력, 방향을 가지는 자료구조를 만든다 

1. 처음의 공들을 입력 받아 큐에 넣는다 - 이때 좌표 주의!

2.  큐에 있는 공들을 큐가 빌 때까지(한 번 비워지는게, 실행 1번 한것) 공을 꺼내서 이동시킨다

3. 이동:

• 이동한 위치 = 처음 위치 + dx[방향] * (속력%전체 칸의 수)
• 음수인 경우를 대비해: 이동한 위치 =  (전체 칸 수 + 이동한 위치 ) % 전체 칸 수 

4. 같은 자리에 여러 개가 있는 경우 대비위해 이동한 것을 ArrayList배열에 넣는다

5. 개수가 1개면 바로 큐에 삽입, 2개 이상이면 조건에 맞게, 속력 방향 변경하여 큐에 삽입

6. 사용한 ArrayList는 초기화 한다.

7. 2~7을 k번 만큼 반복한다.  

 

 

★모듈러 연산★

(a + b) % Mod = ((a % Mod) + (b % Mod)) % Mod
(a - b) % Mod = ((a % Mod) - (b % Mod) + Mod) % Mod
(a * b) % Mod = ((a % Mod) * (b % Mod)) % Mod

 

 

---

2. 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {

	
	static class Fire{ //좌표, 질량, 속력, 방향
		int y, x, m, s, d;
		Fire(int y, int x, int m, int s, int d){
			this.y = y;
			this.x = x;
			this.m = m;
			this.s = s;
			this.d = d;
		}
	}
	//0 ~ 7 까지 방향
	static int[] dx = {0,1,1,1,0,-1,-1,-1};
	static int[] dy = {-1,-1,0,1,1,1,0,-1};
	
	static ArrayList<Fire>[][] map;//파이어볼들이 이동후 담길 곳
	static int n, m, k;
	static Queue<Fire> q = new LinkedList<>();//이동을 할 파이어볼들
	
	public static void main(String[] args) {
		
		Scanner scanner = new Scanner(System.in);
		n = scanner.nextInt();
		m = scanner.nextInt();
		k = scanner.nextInt();
		
		map = new ArrayList[n][n];
		reset();
		
		//좌표가 1부터 시작한다고 하니 -1을 뺀다 
		for(int i = 0; i<m; i++) {
			//y, x, m, s, d;
			q.add(new Fire(scanner.nextInt()-1, scanner.nextInt()-1, scanner.nextInt(), scanner.nextInt(), scanner.nextInt()));
		}
		
		//k번 이동한다
		for(int i = 0; i<k; i++) {
			bfs();
		}
		
		System.out.println(getTotal());
		
		
	}//main
	
	//큐에서 나와서 이동, ArrayList에 넣을거야
	private static void bfs() {
		
		
		//이동 후 arraylist까지 넣기
		while(!q.isEmpty()) {
			Fire f = q.poll();
			int qx = f.x;
			int qy = f.y;
			int qm = f.m;
			int qs = f.s;
			int qd = f.d;
			
			//여기가 이동 부분
			int nx = qx + dx[qd] * (qs%n);
			int ny = qy + dy[qd] * (qs%n);
			
			nx = (nx+n)%n;
			ny = (ny+n)%n;
			
			map[ny][nx].add(new Fire(ny, nx, qm, qs, qd));
			
		}
		
		//arraylist에서 큐에 넣기
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<n; j++) {
				//아무 것도 없다 
				if(map[i][j].size()==0)
					continue;
				
				//딱 한개 있다 - 바로 큐 - 그리고 지워
				else if(map[i][j].size() == 1) {
					q.add(map[i][j].get(0));
				}
				
				//2개 이상이 있다
				else {
					int totalM = map[i][j].get(0).m; //총 질량들의 합 
					int totalS = map[i][j].get(0).s;//총 속력들의 합
					boolean flag = true;//방향들이 일치하는가 판단
					int cnt = map[i][j].size();
					int check = map[i][j].get(0).d%2 == 0? 0:1; //방향이 짝수인가 홀수인가 알아본다
					
					for(int k = 1; k<map[i][j].size(); k++) {
						Fire nf = map[i][j].get(k);
						
						totalM += nf.m;
						totalS += nf.s;
						//방향의 홀짝이 이전것과 다르다면 - 모두 홀수 모두 짝수 아니다
						if(nf.d%2 != check) {
							flag = false;
						}
					}

					totalM = totalM / 5;
					//질량이 0이면 이제 사라진다
					if(totalM == 0)
						continue;
					totalS = totalS / cnt;
					
					//0 2 4 6 - 모두 홀 혹은 짝
					if(flag) {
						for(int dir = 0; dir<=6; dir+=2) {
							q.add(new Fire(i, j, totalM, totalS, dir));
						}
					}
					//1 3 5 7 - 각각 달라
					else {
						for(int dir = 1; dir<=7; dir+=2) {
							q.add(new Fire(i, j, totalM, totalS, dir));
						}
					}
					
					
				}

			}
		}
		
		//map  초기화
		reset();
		
				
	}//bfs
	
	private static void reset() {
		for(int i = 0; i<n; i++) {
			for(int j = 0; j<n; j++) {
				map[i][j] = new ArrayList<>();
			}
		}
	}
	
	//남은 공들의 질량을 구하는 함수 
	private static int getTotal() {
		int mass = 0;
		while(!q.isEmpty()) {
			mass+= q.poll().m;
		}
		return mass;
	}

}

---

3.

삼성 기출 문제이다. 내 기준 기출 문제 중에서는 쉬운 편에 속하는 것 같다.

ArrayList배열을 쓸 수 있게 되어서 좋다

공을 이동시키는 부분이 가장 고민스러웠다.