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

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

[문제링크]

0. 빠트린 부분 없이 잘 구현하면 되는 구현문제 (불가능)

1. 파이어볼 질량은 겹친 파이어볼이 분리될때에만 변경된다

초기 질량합을 구해서 유지, 파이어볼 분리 작업마다 질량합을 수정한다

2. Fireball은 위치 + 질량/방향/속도 값을 가지며, 끊임없이 움직인다

배열 : 여러 fireball을 저장하기 힘들다

List : fireball을 제거/이동하기 힘들다

Stack : push/pop으로 쉽게 이용 가능

이런 이유로 Stack 사용

3. Stack을 가지는 class를 만들어 2차원 배열로 구현, Fireball의 위치 값을 표현했다

4. 이동 이후 Stack의 size가 1보다 크면 분리 작업 수행

import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.Stack; import java.util.StringTokenizer; public class Main{ static class Fireball{ Stackballs; public Fireball() { balls= new Stack<>(); } } static int[][] dir= new int[][] { {-1,0},{-1,1},{0,1},{1,1},{1,0},{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(), " "); int N = pint(st.nextToken()); int M = pint(st.nextToken()); int K = pint(st.nextToken()); int totalW=0; Fireball[][] fireballs = new Fireball[N][N]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { fireballs[i][j]=new Fireball(); } } for (int i = 0; i < M; i++) { int w; st = new StringTokenizer(br.readLine(), " "); fireballs[pint(st.nextToken())-1][pint(st.nextToken())-1] .balls.add(new int[] {w=pint(st.nextToken()),pint(st.nextToken()),pint(st.nextToken())}); totalW+=w; } for (int i = 0; i < K; i++) { List l = new ArrayList<>(); //이동 시작 for (int j = 0; j < N; j++) { for (int j2 = 0; j2 < N; j2++) { while(!fireballs[j][j2].balls.isEmpty()) { int[] ball = fireballs[j][j2].balls.pop(); int x = j + dir[ball[2]][0]*ball[1]+N; int y = j2+ dir[ball[2]][1]*ball[1]+N; x%=N; if(x<0)x+=N; y%=N; if(y<0)y+=N; l.add(new int[] {x,y,ball[0],ball[1],ball[2]}); } } } for (int[] b : l) { fireballs[b[0]][b[1]].balls.add(new int[] {b[2],b[3],b[4]}); } //이동 끝 for (int j = 0; j < N; j++) { for (int j2 = 0; j2 < N; j2++) { int size=0; if( (size = fireballs[j][j2].balls.size()) >1) { boolean same = true; int[] ball=fireballs[j][j2].balls.pop(); int ballW = ball[0];//m,s,d int ballS = ball[1]; int fstDir = ball[2]%2; int newDir=0; for (int o = 1; o < size; o++) { ball=fireballs[j][j2].balls.pop(); ballW += ball[0];//m,s,d ballS += ball[1]; if(fstDir != ball[2]%2)same=false; } totalW-=ballW; ballW/=5; ballS/=size; totalW+=ballW*4; if(ballW==0)continue;//0이면 소멸 if(!same)newDir=1; for (int o = 0; o < 4; o++) { fireballs[j][j2].balls.add(new int[] {ballW, ballS, newDir}); newDir+=2; } } } }//겹친 파이어볼 분리 끝 }//K번 실행 끝 System.out.println(totalW); } static int pint(String s) { return Integer.parseInt(s); } }

결과 화면

from http://nato-blog.tistory.com/128 by ccl(S) rewrite - 2021-09-08 08:27:20