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

보통 (r,c)로 주어지니 (y,x)로 받아야한다!!

이틀만에 성공했다...

 

grid는 x,y를 row col을 이처럼 적용해야된다.

 

보통 (r,c)로 주어지니 (y,x)로 받아야한다!!

(r,c)로 주어지면 (y,x)로 받아야함.

 

우선 아래 코드에서는 x,y값을 반대로 적용했다.

r,c 를 x,y에 받으면 생기는 일

그래서 문제 푸는내내 계속 헷갈렸다.

 

 

가장 큰 실수는 

잘못된 부분은 아래에 정리하겠다.

import java.util.*;

class Main {
​​​​public static int N, M, K;
​​​​public static ArrayList<ArrayList<Queue<Fireball>>> fireball;
​​​​public static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
​​​​public static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};

​​​​public static void main(String[] args) {
​​​​​​​​Scanner sc = new Scanner(System.in);
​​​​​​​​N = sc.nextInt();
​​​​​​​​M = sc.nextInt();
​​​​​​​​K = sc.nextInt();
​​​​​​​​fireball = new ArrayList<>();
​​​​​​​​for (int i = 0; i <= N; i++) {//0~N
​​​​​​​​​​​​fireball.add(new ArrayList<>());
​​​​​​​​​​​​for (int j = 0; j <= N; j++) fireball.get(i).add(new LinkedList<>());//0~N
​​​​​​​​}
​​​​​​​​for (int i = 0; i < M; i++) {
​​​​​​​​​​​​int r = sc.nextInt();
​​​​​​​​​​​​int c = sc.nextInt();
​​​​​​​​​​​​int m = sc.nextInt();
​​​​​​​​​​​​int s = sc.nextInt();
​​​​​​​​​​​​int d = sc.nextInt();
​​​​​​​​​​​​fireball.get(r).get(c).offer(new Fireball(m, s, d));
​​​​​​​​}
​​​​​​​​//input끝
​​​​​​​​for (int k = 0; k < K; k++) {
​​​​​​​​​​​​//System.out.println("kkkkkkkkkk" + k);
​​​​​​​​​​​​move(k);//이동
​​​​​​​​​​​​// System.out.println("split");
​​​​​​​​​​​​sumSplit(k);
​​​​​​​​}

​​​​​​​​System.out.println(print());
​​​​}

​​​​static int print() {
​​​​​​​​int sum = 0;
​​​​​​​​for (int i = 1; i <= N; i++) {
​​​​​​​​​​​​for (int j = 1; j <= N; j++) {
​​​​​​​​​​​​​​​​while (!fireball.get(i).get(j).isEmpty()) {
​​​​​​​​​​​​​​​​​​​​Fireball b = fireball.get(i).get(j).poll();
​​​​​​​​​​​​​​​​​​​​sum += b.m;
​​​​​​​​​​​​​​​​​​​​//System.out.println("안뽀개진거:"+i+","+j);
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}
​​​​​​​​return sum;
​​​​}

​​​​static class Fireball {
​​​​​​​​int m, s, d;
​​​​​​​​int kcount = 0;

​​​​​​​​Fireball(int m, int s, int d) {
​​​​​​​​​​​​this.m = m;//질량
​​​​​​​​​​​​this.s = s;//몇칸이동
​​​​​​​​​​​​this.d = d;//방향
​​​​​​​​}

​​​​​​​​Fireball(int m, int s, int d, int k) {
​​​​​​​​​​​​this.kcount = k;
​​​​​​​​​​​​this.m = m;//질량
​​​​​​​​​​​​this.s = s;//몇칸이동
​​​​​​​​​​​​this.d = d;//방향
​​​​​​​​}
​​​​}

​​​​static void move(int k) {
​​​​​​​​for (int i = 1; i <= N; i++) {
​​​​​​​​​​​​for (int j = 1; j <= N; j++) {
​​​​​​​​​​​​​​​​if (fireball.get(i).get(j).isEmpty()) continue;
​​​​​​​​​​​​​​​​int size = fireball.get(i).get(j).size();
​​​​​​​​​​​​​​​​for (int s = 0; s < size; s++) {
​​​​​​​​​​​​​​​​​​​​Fireball b = fireball.get(i).get(j).poll();
​​​​​​​​​​​​​​​​​​​​if (b.kcount > k) {
​​​​​​​​​​​​​​​​​​​​​​​​fireball.get(i).get(j).offer(b);
​​​​​​​​​​​​​​​​​​​​​​​​continue;//이미 k번째
​​​​​​​​​​​​​​​​​​​​} else {//현위치 i,j
​​​​​​​​​​​​​​​​​​​​​​​​//System.out.print("(" + i + "," + j + ")");
​​​​​​​​​​​​​​​​​​​​​​​​b.kcount += 1;
​​​​​​​​​​​​​​​​​​​​​​​​int x = i + ((b.s % N) * dx[b.d]);
​​​​​​​​​​​​​​​​​​​​​​​​int y = j + ((b.s % N) * dy[b.d]);

​​​​​​​​​​​​​​​​​​​​​​​​if (x > 1) x = x % N;//업오버플로우
​​​​​​​​​​​​​​​​​​​​​​​​if (x < 1) x = N - Math.abs(x);//다운오버플로우

​​​​​​​​​​​​​​​​​​​​​​​​if (y > 1) y = y % N;//업오버플로우
​​​​​​​​​​​​​​​​​​​​​​​​if (y < 1)
​​​​​​​​​​​​​​​​​​​​​​​​​​​​y = N - Math.abs(y);//다운오버플로우

​​​​​​​​​​​​​​​​​​​​​​​​fireball.get(x).get(y).offer(b);

​​​​​​​​​​​​​​​​​​​​​​​​//System.out.println("->(" + x + "," + y + ")"+b.d);
​​​​​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}

​​​​static void sumSplit(int k) {
​​​​​​​​++k;
​​​​​​​​for (int i = 1; i <= N; i++) {
​​​​​​​​​​​​for (int j = 1; j <= N; j++) {
​​​​​​​​​​​​​​​​int size = fireball.get(i).get(j).size();
​​​​​​​​​​​​​​​​if (size >= 2) {//2이상이면 합쳐
​​​​​​​​​​​​​​​​​​​​int split_m = 0, split_s = 0, split_d = 0;
​​​​​​​​​​​​​​​​​​​​for (int sz = 0; sz < size; sz++) {
​​​​​​​​​​​​​​​​​​​​​​​​Fireball b = fireball.get(i).get(j).poll();
​​​​​​​​​​​​​​​​​​​​​​​​split_m += b.m;
​​​​​​​​​​​​​​​​​​​​​​​​split_d += b.d % 2;
​​​​​​​​​​​​​​​​​​​​​​​​split_s += b.s;
​​​​​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​​​​​split_m = split_m / 5;
​​​​​​​​​​​​​​​​​​​​if (split_m == 0) {
​​​​​​​​​​​​​​​​​​​​​​​​//System.out.println("뽀각");
​​​​​​​​​​​​​​​​​​​​​​​​continue;
​​​​​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​​​​​//질량0이면 패스------------
​​​​​​​​​​​​​​​​​​​​split_s = split_s / size;
​​​​​​​​​​​​​​​​​​​​//System.out.println("s:" + split_s);
​​​​​​​​​​​​​​​​​​​​if (split_d == size || split_d == 0) {//모두 홀수(2n+2k+2l)+size거나 짝수 0246
​​​​​​​​​​​​​​​​​​​​​​​​fireball.get(i).get(j).offer(new Fireball(split_m, split_s, 0, k));
​​​​​​​​​​​​​​​​​​​​​​​​fireball.get(i).get(j).offer(new Fireball(split_m, split_s, 2, k));
​​​​​​​​​​​​​​​​​​​​​​​​fireball.get(i).get(j).offer(new Fireball(split_m, split_s, 4, k));
​​​​​​​​​​​​​​​​​​​​​​​​fireball.get(i).get(j).offer(new Fireball(split_m, split_s, 6, k));
​​​​​​​​​​​​​​​​​​​​} else {//1357
​​​​​​​​​​​​​​​​​​​​​​​​fireball.get(i).get(j).offer(new Fireball(split_m, split_s, 1, k));
​​​​​​​​​​​​​​​​​​​​​​​​fireball.get(i).get(j).offer(new Fireball(split_m, split_s, 3, k));
​​​​​​​​​​​​​​​​​​​​​​​​fireball.get(i).get(j).offer(new Fireball(split_m, split_s, 5, k));
​​​​​​​​​​​​​​​​​​​​​​​​fireball.get(i).get(j).offer(new Fireball(split_m, split_s, 7, k));
​​​​​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​​​​​}
​​​​​​​​​​​​}
​​​​​​​​}
​​​​}
}

하이라이트부분.

1~N을 초과/미만인 좌표는 서로 연결된다.

즉, 그리드 인덱스 오버플로우시 0=>N으로, N+1=>1로 바꿔주라는 뜻이다.

 

이 부분에서 mod연산을 하는 와중 실수가 계속되었다.

해결에 도움을 준 질문/답변자에게 감사의 링크를 남긴다.(www.acmicpc.net/board/view/66407)

int x = i + ((b.s % N) * dx[b.d]);
int y = j + ((b.s % N) * dy[b.d]);

f (x > 1) x = x % N;//업오버플로우
if (x < 1) x = N - Math.abs(x);//다운오버플로우

if (y > 1) y = y % N;//업오버플로우
if (y < 1) y = N - Math.abs(y);//다운오버플로우

fireball.get(x).get(y).offer(b);

나는 내가 mod연산을 잘 했다고 생각했는데, 다른방식으로 다시 연산하니 성공하였다.

아마 계산해보지 못한 경우의 수가 남아있던 것 같다.

 

두가지 추가 테스트케이스를 남겨두겠다.

4 6 4
1 1 5 1 1
3 3 5 1 5
1 3 5 1 3
3 1 5 1 7
2 2 5 1 3
3 2 5 1 2

-> 4

 

4 9 5
3 2 8 5 2
3 3 19 3 4
3 1 7 1 1
4 4 6 4 0
2 1 6 2 5
4 3 9 4 3
2 2 16 1 2
4 2 17 5 3
3 4 3 5 7

-> 33