[ 백준 20056] 마법사 상어와 파이어볼 - Java 반례

문제 링크

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

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

문제 풀이

풀다보면 딱 삼성 코딩테스트 문제같다고 느끼는 시뮬레이션 문제이다.

 

배열을 생성해서 풀 필요없이 자료구조를 이용해서 풀었다.

 

테스트 케이스까지 금방 맞았지만 제출했을때 자꾸 틀려서 한참 고민했던 문제...

 

나처럼 파이어볼이 이동할때를 나머지로 처리해서 풀었을 때 반례를 생각해 보면,

 

속도가 굉장히 높을때를 생각해서 구현하는 것도.. 중요할 것 같다.

 

반례

 

7 5 3
1 3 5 13 4
2 3 5 13 6
5 2 9 13 7
6 2 1 13 5
4 4 2 13 2

 

답: 22

소스 코드

package com.kyobobook.comm.util;

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

class FireBall implements Comparable<FireBall>{
	int N;
	int x;
	int y;
	int m;
	int s;
	int d;

	@Override
	public int compareTo(FireBall o) {
		Integer o1 = N*x + y;
		Integer o2 = N*o.x + o.y;

		return o1.compareTo(o2);
	}

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

}

public class Sol {
	static int [] dx = { -1, -1, 0 , 1, 1,  1, 0, -1};
	static int [] dy = { 0 , 1 , 1 , 1, 0, -1,-1, -1};
	static int N;
	static int M;
	static int K;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		//파이어볼들을 이동시킨다.
		// 큐를 만들어서 파이어볼들을 넣어놓는다.
		// 위치순으로 정렬시킨다.
		//파이어볼을 합친다. -> 어떻게 찾아서 합치는가?
		//

		N = sc.nextInt(); // 격자크기
		M = sc.nextInt(); // 파볼갯수
		K = sc.nextInt(); // 명령갯수

		Queue<FireBall> balls = new PriorityQueue<FireBall>();
		for (int i = 0; i < M; i++) {
			balls.add(new FireBall(N,sc.nextInt()-1, sc.nextInt()-1, sc.nextInt(), sc.nextInt(), sc.nextInt()));
		}

		for (int i = 0; i < K; i++) {
			balls = order(balls);
		}

		int sum =0;
		while(!balls.isEmpty()) {
			sum+=balls.poll().m;
		}
		System.out.println(sum);

	}

	static Queue<FireBall> order(Queue<FireBall> balls) {
		balls = move(balls);
		balls = merge(balls);
		return balls;
	}

	static Queue<FireBall> move(Queue<FireBall> balls) {
		Queue<FireBall> temp = new PriorityQueue<FireBall>();

		while(!balls.isEmpty()) {
			FireBall ele = balls.poll();
			int nx = ((ele.x + dx[ele.d] *ele.s)+10000*N)%N;
			int ny = ((ele.y + dy[ele.d] *ele.s)+10000*N)%N;
			ele.x = nx;
			ele.y = ny;
			temp.add(ele);
		}
		return temp;

	}

	static Queue<FireBall> merge(Queue<FireBall> balls) {
		Queue<FireBall> temp = new PriorityQueue<FireBall>();
		while(!balls.isEmpty()) {
			FireBall ele = balls.poll();
			boolean isMerge = false;
			Queue<FireBall> mergeTemp = new PriorityQueue<FireBall>();


			while(!balls.isEmpty() ) {
				FireBall peek = balls.peek();
				if(ele.x*N +ele.y != peek.x*N + peek.y) break;
				isMerge =true;
				mergeTemp.add(balls.poll());
			}

			if(isMerge) {
				mergeTemp.add(ele);
				int num = mergeTemp.size();
				int m=0 ; // 질량
				int d=mergeTemp.peek().d%2 ; // 방향
				int s=0 ; // 속력
				boolean dir=true;
				while(!mergeTemp.isEmpty()) {
					FireBall tmp = mergeTemp.poll();
					m +=tmp.m;
					s +=tmp.s;
					dir = d==tmp.d%2 ? dir :false;
				}
				if(m/5 ==0) continue;
				if(dir) {
					temp.add(new FireBall(N,ele.x, ele.y, m/5, s/num, 0));
					temp.add(new FireBall(N,ele.x, ele.y, m/5, s/num, 2));
					temp.add(new FireBall(N,ele.x, ele.y, m/5, s/num, 4));
					temp.add(new FireBall(N,ele.x, ele.y, m/5, s/num, 6));
				}else {
					temp.add(new FireBall(N,ele.x, ele.y, m/5, s/num, 1));
					temp.add(new FireBall(N,ele.x, ele.y, m/5, s/num, 3));
					temp.add(new FireBall(N,ele.x, ele.y, m/5, s/num, 5));
					temp.add(new FireBall(N,ele.x, ele.y, m/5, s/num, 7));
				}

			}else	temp.add(ele);
		}
		return temp;

	}

}