[BOJ20056/Java] 마법사 상어와 파이어볼

문제 요약

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

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

문제에서 봐야하는 유의사항이 많기 때문에 주의가 필요한 문제이다.

하나하나 빠지지 않고 체크하는 것이 중요.

1. map의 연결(1번 행과 N번 행, 1번 열과 N번 열)

2. 파이어볼의 이동 방향

3. 파이어볼 이동 방식

4. 파이어볼 합치고 나누기

    - 질량

    - 속력

    - 방향

    - 소멸

입/출력

-> 파이어볼 정보 순서가 r, c, m, s, d 로 주어진다.. 착각하면 안됨...(왜안되지 진지하게 고민하고 있었음)

 

접근 아이디어

1. map의 연결과 이동 방식

    -> 파이어볼을 이동시킬 때 범위를 벗어나지 않도록 하기 위해서 속력을 N으로 나눈 나머지(혹시 음수일 수도 있어서 N을 한번 더 더해주고)와 방향, 현재 위치를 고려하고 이를 또 다시 N으로 나눠서 그 다음 위치를 정한다.

void moveFire() {
	r = (r+dir[d][0]*(s%N)+N)%N;
	c = (c+dir[d][1]*(s%N)+N)%N;
}

 

2. 파이어볼의 이동 방향

    -> 파이어볼의 이동 방향을 문제에서 번호별로 줬다. 이를 dir 배열로 정의해서 관리!

 

4. 파이어볼 합치고 나누기

    ->이부분을 어떻게 효율적으로 할 수 있을지 고민해봤는데, 그냥 각칸마다 리스트를 통해서 관리하는 방법을 사용하기로 했다.

    - 질량 -> 걍 더하면 됨

    - 속력

        -> 속력에서 주의해야하는 것은 처음 입력받을 때부터 속력 계산을 쉽게 하기 위해서 s%N으로 받아버리면 이 때 나눠지는 파이어볼들의 속력에 영향이 간다. 입력받을 때는 초기 값을 저장해두고 이동시에만 빠른 계산을 고려하자.

    - 방향

        -> 방향을 고려하기 위해서 방향이 홀수인 경우, 짝수인 경우를 각각 카운트하고 모두 홀수 또는 짝수 즉 둘 중 하나의 카운트가 0이라면 방향을 0,2,4,8로 줄 수 있도록 했다.

    - 소멸 -> 질량 값에 따라서 리스트에 추가하지 않을 수 있음

 

시간 복잡도

지금 구현상으로는 K*N*N*M이다...

시간 복잡도 자체를 어떻게 줄일 수 있을지 고민을 많이해봤는데

구현문제라서 크게 신경쓰지 않기로 했다.

구현 코드

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

public class Main {

	static int[][] dir = {
			{-1, 0}, {-1, 1}, {0, 1}, {1, 1},
			{1, 0}, {1, -1}, {0, -1}, {-1, -1}
	};
	
	static class Fire{
		int r, c, m, d, s;
		
		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;
		}
		
		void moveFire() {
			r = (r+dir[d][0]*(s%N)+N)%N;
			c = (c+dir[d][1]*(s%N)+N)%N;
		}
	}
	
	static int N, M, K;
	static ArrayList<Fire> ball = new ArrayList<>();
	static ArrayList<Fire>[][] map;
	
	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());
		map = new ArrayList[N][N];
		int total = 0;
		for(int i = 0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken())-1;
			int c = Integer.parseInt(st.nextToken())-1;
			int m = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			
			ball.add(new Fire(r,c,m,s,d));
			total += m;
		}
		
		for(int i = 0; i<N; i++) {
			for(int j = 0; j<N; j++) {
				map[i][j] = new ArrayList<>();
			}
		}
		
		for(int k = 0; k<K; k++) {
			for(int i = 0; i<N; i++) {
				for(int j = 0; j<N; j++) {
					map[i][j].clear();
				}
			}
			
			for (Fire f : ball) {
				f.moveFire();
				map[f.r][f.c].add(f);
			}
			
			for(int i = 0; i<N; i++) {
				for(int j = 0; j<N; j++) {
					ArrayList<Fire> temp = map[i][j];
					int size = temp.size();
					if(temp.size()<=1) continue;
					int m = 0, s = 0, d;
					int ocnt = 0, ecnt = 0;
					for (Fire fire : temp) {
						m+=fire.m;
						s+=fire.s;
						if(fire.d%2 == 0) ecnt++;
						else ocnt++;
						ball.remove(fire);
					}
					total -= m;
					m /= 5;
					s /= size;
					if(ocnt == 0 || ecnt == 0) d = 0;
					else d = 1;
					if(m <= 0) continue;
					for(int f = 0; f<4; f++) {
						ball.add(new Fire(i, j, m, s, d+f*2));
					}
					total += 4*m;
				}
			}
		}
		
		System.out.println(total);
		
	}

}