[백준] 20056번 마법사 상어와 파이어볼 (자바 풀이)

문제

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

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

 

풀이

코드를 짜는 것보다 예외를 처리하는게 훨씬 어려웠던 문제였다.

 

우선 다음과 같은 Fireball 클래스를 만들었다.

 

public static class Fireball{
		int r;	// 행
		int c;	// 열
		int m;	// 질량
		int s;	// 속력
		int d;	// 방향
		Fireball(int r,int c,int m, int s,int d){
			this.r = r ;
			this.c = c;
			this.m = m;
			this.s = s;
			this.d = d;
		}
	}

 

이후 2차원 ArrayList<Fireball> map[][] 배열과, Fireball들을 모아놓은 ArrayList<Fireball> list를 따로 만들었다.

 

K번의 이동과 합병 과정을 거치기 위해 다음과 같이 move() 함수와 merge() 함수를 따로 만들었다.

 

public static void move() {
		for(int i=1; i<N+1; i++) {
			for(int j=1; j<N+1; j++) {
				map[i][j] = new ArrayList<Fireball>();
			}
		}
		
		for(Fireball cur : list) {
			cur.r = cur.r+dx[cur.d]*(cur.s%N);
			cur.c = cur.c+dy[cur.d]*(cur.s%N);
			
			if(cur.r > N) cur.r %= N;
			if(cur.c > N ) cur.c %= N;
			if(cur.r <= 0 ) cur.r = N-Math.abs(cur.r);
			if(cur.c <= 0) cur.c = N-Math.abs(cur.c);
			
			map[cur.r][cur.c].add(cur);
		}
		
	}

 

파이어볼이 이동하는 함수는 위와같이 모든 map의 원소를 초기화한뒤, list에 담겨있던 파이어볼들의 위치를 바꿔준뒤, map에 추가해주는 식으로 작성했다. 여기서, 속력은 모듈러 연산을 해주어 배열의 범위를 벗어나지 않도록 해준다. 

 

나는 이 부분에서 오류가 많이 발생했다. 기존에는 cur.r + (dx[cur.d]*cur.s)%N 이렇게 계산을 해주었는데, 이런 식으로 작성하면 만약 cur.r이 N과 같다면 0이 되어버리게 된다. 따라서 위와 같이 작성해야 한다.

 

public static void merge(int x, int y) {
		int sumM=0, sumS=0, sumCnt=0, sumD=0;
		boolean isEven = true;
		boolean isOdd = true;
		for(Fireball cur : map[x][y]) {
			sumM += cur.m;
			sumS += cur.s;
			sumCnt++;
			if(cur.d %2 ==0) {
				isOdd = false;
			}else {
				isEven = false;
			}
		}
		
		int M = sumM/5;
		int S = sumS/sumCnt;
		
		map[x][y] = new ArrayList<>();
		if(M <= 0) {
			return;
		}
		
		if(isEven || isOdd) {
			for(int i=0; i<4; i++) {
				map[x][y].add(new Fireball(x,y,M,S,i*2));
			}
		}else {
			for(int i=0; i<4; i++) {
				map[x][y].add(new Fireball(x,y,M,S,i*2+1));
			}
		}
		
	}

 

파이어볼들을 합치는 과정은 위와 같다. 나는 처음엔 모든 수가 홀수 혹은 짝수인것은 모든 수를 합쳤을 때 짝수라면 해당한다고 생각했는데, [0,1,2,3]와 같은 반례가 있다는 것을 나중에 알게 되었다. 

 

따라서 모든 수가 홀수인지 짝수인지는 위와 같이 boolean flag를 이용해 해결했다.

 

다른 부분은 지문에 나온 그대로 구현했다.

 

이렇게 move() 과정과 merge() 과정을 완료했으면 makeList()라는 함수를 통해 파이어볼들을 담은 리스트를 다시 만들어준다. 

 

위와 같은 과정을 K번 반복하고 남은 파이어볼들의 질량을 계산해주면 된다.

 

구현 문제는 꼼꼼함과 예외처리가 힘든 것 같다.

 

 

코드

 

import java.io.*;
import java.util.*;


public class Baekjoon_20056 {
	static int N,M,K;
	static ArrayList<Fireball> map[][];
	static ArrayList<Fireball> list = new ArrayList<>();
	static int dx[] = {-1,-1,0,1,1,1,0,-1};
	static int dy[] = {0,1,1,1,0,-1,-1,-1};
 	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+1][N+1];
		for(int i=0; i<N+1; i++) {
			for(int j=0; j<N+1; j++) {
				map[i][j] = new ArrayList<Fireball>();
			}
		}
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			map[r][c].add(new Fireball(r,c,m,s,d));
			list.add(new Fireball(r,c,m,s,d));
		}
		
		//print();
		
		while(K-- > 0) {
			move();
			//print();
			for(int i=1; i<N+1; i++) {
				for(int j=1; j<N+1; j++) {
					if(map[i][j].size() >=2 ) {
						merge(i,j);
						//print();
					}
				}
			}
			makeList();
		}
		
		int ans = 0;
		for(int i=1; i<N+1; i++) {
			for(int j=1; j<N+1; j++) {
				if(map[i][j].size() > 0) {
					for(Fireball cur : map[i][j]) {
						//System.out.println(cur.m);
						ans += cur.m;
						
					}
				}
			}
		}
		
		System.out.println(ans);
	}
 	
 	public static void makeList(){
 		list = new ArrayList<>();
 		for(int i=1; i<N+1; i++) {
 			for(int j=1; j<N+1; j++) {
 				if(map[i][j].size() > 0){
 					for(Fireball cur : map[i][j]) {
 						list.add(cur);
 					}
 				}
 			}
 		}
 	}
 	
 	public static void print() {
 		for(int i=1; i<N+1; i++) {
 			for(int j=1; j<N+1; j++) {
 				System.out.print(map[i][j].size() +" ");
 			}
 			System.out.println();
 		}
 		System.out.println();
 	}
	
	public static void move() {
		for(int i=1; i<N+1; i++) {
			for(int j=1; j<N+1; j++) {
				map[i][j] = new ArrayList<Fireball>();
			}
		}
		
		for(Fireball cur : list) {
			cur.r = cur.r+dx[cur.d]*(cur.s%N);
			cur.c = cur.c+dy[cur.d]*(cur.s%N);
			
			if(cur.r > N) cur.r %= N;
			if(cur.c > N ) cur.c %= N;
			if(cur.r <= 0 ) cur.r = N-Math.abs(cur.r);
			if(cur.c <= 0) cur.c = N-Math.abs(cur.c);
			
			map[cur.r][cur.c].add(cur);
		}
		
	}
	
	public static void merge(int x, int y) {
		int sumM=0, sumS=0, sumCnt=0, sumD=0;
		boolean isEven = true;
		boolean isOdd = true;
		for(Fireball cur : map[x][y]) {
			sumM += cur.m;
			sumS += cur.s;
			sumCnt++;
			if(cur.d %2 ==0) {
				isOdd = false;
			}else {
				isEven = false;
			}
		}
		
		int M = sumM/5;
		int S = sumS/sumCnt;
		
		map[x][y] = new ArrayList<>();
		if(M <= 0) {
			return;
		}
		
		if(isEven || isOdd) {
			for(int i=0; i<4; i++) {
				map[x][y].add(new Fireball(x,y,M,S,i*2));
			}
		}else {
			for(int i=0; i<4; i++) {
				map[x][y].add(new Fireball(x,y,M,S,i*2+1));
			}
		}
		
	}
	
	public static class Fireball{
		int r;	// 행
		int c;	// 열
		int m;	// 질량
		int s;	// 속력
		int d;	// 방향
		Fireball(int r,int c,int m, int s,int d){
			this.r = r ;
			this.c = c;
			this.m = m;
			this.s = s;
			this.d = d;
		}
	}

}