[백준] 20056 마법사 상어와 파이어볼

1. 문제

www.acmicpc.net/problem/20056

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

 

 

 

 

2. 접근방법

조금 복잡한 시뮬레이션 문제

두가지 스텝이 있는데

 

첫번째가 파이어볼을 이동시키기

두번째가 같은위치의 파이어볼은 합해서 나누기

 

처음 입력으로 들어온 파이어볼들을 Arraylist로 넣어주고

하나씩 빼서 이동을 시켜준다.

 

파이어볼을 이동시키는것은 한방향으로만 속력만큼 이동을 하는데

1과 N은 연결 되어 있으니 N번마다 제자리로 돌아오게 된다.

위 사항만 고려해서 이동 위치를 구하면 된다.

 

나는 같은위치에 모이는 파이어볼들을 모으기 위해

HashMap으로 키를 row*1000 + col 으로 주고 값을 Arraylist로 지정해서 모았다.

 

이후 HashMap에 저장된 모든 키에 대해서

List를 꺼내서 1개인 경우와 1개보다 큰 경우로 나눠서

문제에 제시된 대로 계산을 한뒤 arraylist에 다시 넣어주었다.

 

이것을 k번 반복한뒤

리스트에 남아있는 파이어볼들의 질량의 합을 구해 답을 구했다.

3. 자바 코드

package Gold;

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

public class P20056마법사상어와파이어볼 {
	static class fireball {
		int x;
		int y;
		int m;
		int s;
		int d;

		public fireball(int x, int y, int m, int s, int d) {
			this.x = x;
			this.y = y;
			this.m = m;
			this.s = s;
			this.d = d;
		}

		public fireball() {
		}

	}

	static int N, M, K;
	static ArrayList<fireball> firelist = new ArrayList<fireball>();
	static HashMap<Integer, List<fireball>> dupli = new HashMap<Integer, List<fireball>>();
	static int dir[][] = {{0,2,4,6},{1,3,5,7}};
	

	public static void main(String[] args) throws Exception {
		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());
		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 s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			firelist.add(new fireball(x, y, m, s, d));
		}
		for (int i = 0; i < K; i++) {// simul
			move();
			fillList();
		}
		int result = 0;
		for(fireball f : firelist)
			result += f.m;
		System.out.println(result);
	}

	static int dr[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
	static int dc[] = { 0, 1, 1, 1, 0, -1, -1, -1 };

	static void move() {
		for(fireball now : firelist) {
			int row = now.x + dr[now.d] * now.s;
			int col = now.y + dc[now.d] * now.s;
			if (row < 0) {
				row = (N - (Math.abs(row) % N));
			}
			if (row >= N) {
				row = (row % N);
			}
			if (col < 0) {
				col = (N - (Math.abs(col) % N));
			}
			if (col >= N) {
				col = (col % N);
			}
			int key = row*1000+col;
			if(dupli.get(key) == null) {
				dupli.put(key, new ArrayList<fireball>());
			}
			dupli.get(key).add(new fireball(row, col, now.m, now.s, now.d));
		}
		firelist.clear();
	}
	
	static void fillList() {
		for(int key : dupli.keySet()) {
			List<fireball> nowlist = dupli.get(key);
			if(nowlist.size() == 1) {
				fireball now = nowlist.get(0);
				firelist.add(new fireball(now.x, now.y, now.m, now.s, now.d));
				continue;
			}
			fireball first = nowlist.get(0);
			boolean allsame = true;
			int x = first.x;
			int y = first.y;
			int firstd = first.d; 
			int sumM = first.m;
			int sumS = first.s;
			for(int i = 1 ; i < nowlist.size() ; i++) {
				fireball now = nowlist.get(i);
				sumM += now.m;
				sumS += now.s;
				if((firstd + now.d) %2 == 1) {
					allsame = false;
				}
			}
			sumM = sumM/5;
			sumS = sumS/nowlist.size();
			if(sumM == 0)
				continue;
			int d = allsame ? 0 : 1;
			for(int i = 0 ; i < 4 ; i++) {
				firelist.add(new fireball(x, y, sumM, sumS, dir[d][i]));
			}
			
		}
		dupli.clear();
	}

}

4. 마치며

맵이 반복되니깐 mod N을 하면 되는 부분에서 헤매느라 오래 걸렸다..