[백준/BOJ] 20056 마법사 상어와 파이어볼 - JAVA
[백준/BOJ] 20056 마법사 상어와 파이어볼 - JAVA
문제
https://www.acmicpc.net/problem/14939
문제 분석
조건
N x N 크기의 격자에서 M개의 파이어볼이 주어진 정보(위치, 질량, 속력, 방향)를 가지고 움직인다. K번의 명령을 수행하는 동안, 파이어볼은 다음과 같은 규칙에 따라 동작한다.
- 모든 파이어볼이 자신의 방향과 속력대로 이동한다. 격자는 연결되어 있어, 1번 행의 위는 N번 행과, N번 열의 오른쪽은 1번 열과 연결된다.
- 이동 후, 한 칸에 2개 이상의 파이어볼이 모이면 하나로 합쳐진 뒤 4개로 나뉜다.
- 질량: (합쳐진 질량의 합) / 5
- 속력: (합쳐진 속력의 합) / (합쳐진 파이어볼 개수)
- 방향: 합쳐진 파이어볼들의 방향이 모두 홀수거나 짝수이면 0, 2, 4, 6, 그렇지 않으면 1, 3, 5, 7이 된다.
- 질량이 0인 파이어볼은 소멸된다.
- K번의 명령 후, 남아있는 모든 파이어볼의 질량의 합을 구하는 문제이다.
풀이방법
`Fireball`클래스를 정의하였고, 이동을 담당하는 메서드를 정의하였다. 매 명령마다 이동하는 `Fireball`을 관리하기 위해 `Queue`를 이용하였고, 이동 후 `map`에 넣어 주었다.
큐에 든 모든 `Fireball`이 이동을 마친 뒤, map을 살피며 합치고 나눠주는 과정을 구현하였다.
상어 문제답게 상태 관리를 하며 구현하는 문제이다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Fireball {
static int[][] dirs = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
int r, c, m, d, s;
public Fireball(int r, int c, int m, int d, int s) {
this.r = r;
this.c = c;
this.m = m;
this.d = d;
this.s = s;
}
public void move(int N) {
r = ((r + dirs[d][0] * s) % N + N) % N;
c = ((c + dirs[d][1] * s) % N + N) % N;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
List<Fireball>[][] map = new ArrayList[N][N];
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
map[r][c] = new ArrayList<>();
}
}
List<Fireball> fireballs = new ArrayList<>();
for (int i = 0; i < M; i++) {
initFireball(br, fireballs);
}
// K번 명령
for (int i = 0; i < K; i++) {
// 이동
for (Fireball fireball : fireballs) {
fireball.move(N);
map[fireball.r][fireball.c].add(fireball);
}
fireballs = new ArrayList<>();
// 합치기
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (map[r][c].size() > 1) { // 파이어볼이 여러개.
int m = 0; // 질량
int s = 0; // 속도
int evenCount = 0; // 방향 정하기 위함
int oddCount = 0;
for (Fireball fireball : map[r][c]) {
m += fireball.m;
s += fireball.s;
if (fireball.d % 2 == 0) {
evenCount++;
} else {
oddCount++;
}
}
m = m / 5;
s = s / (evenCount + oddCount);
if (m > 0) { // 질량이 0이면 사라지므로 0이상일때만 나누기
splitFireball(fireballs, map, r, c, m, s, evenCount, oddCount);
}
} else if (map[r][c].size() == 1) { // 칸에 파이어볼 1개
fireballs.add(map[r][c].get(0));
}
map[r][c].clear();
}
}
}
//파이어볼 질량 합
int answer = 0;
for (Fireball fireball : fireballs) {
answer += fireball.m;
}
System.out.println(answer);
}
private static void splitFireball(List<Fireball> fireballs, List<Fireball>[][] map, int r, int c, int m, int s, int evenCount, int oddCount) {
if (evenCount * oddCount == 0) {// 합쳐지는 파이어볼 방향이 모두 홀수거나 짝수
fireballs.add(new Fireball(r, c, m, 0, s));
fireballs.add(new Fireball(r, c, m, 2, s));
fireballs.add(new Fireball(r, c, m, 4, s));
fireballs.add(new Fireball(r, c, m, 6, s));
} else {
fireballs.add(new Fireball(r, c, m, 1, s));
fireballs.add(new Fireball(r, c, m, 3, s));
fireballs.add(new Fireball(r, c, m, 5, s));
fireballs.add(new Fireball(r, c, m, 7, s));
}
}
private static void initFireball(BufferedReader br, List<Fireball> fireballs) throws IOException {
StringTokenizer st;
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());
fireballs.add(new Fireball(r, c, m, d, s));
}
}주절주절
ㅋㅋㅋ..... 어려운 문제가 아니다. 근데 왜 이런 일이 있어났는가....ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ큐ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ 저기 저 2배가 늘었다 줄었다 반복하는 메모리가 보이시나요...?ㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜㅜ 심지어 3배까지도 늘어나고..ㅋㅋ
하...ㅋㅋㅋ 제출해 보니 역시나 풀었던 문제이고... 그치만 2년 전 메모리가 압도적으로 적게 사용? 2배면 쫌 심각한데? 싶어서 코드 뜯어보는데
/**
* 마법사 상어와 파이어볼 / 골드4 / 1시간 30분 / 2023년 3월 6일
* https://www.acmicpc.net/problem/20056
*/
class FireBall {
private int r, c, m, d, speed;
/**
* 중략
*/
}
class Pos {
private int r, c;
private FireBall ball;
/**
* 중략
*/
}
public class Main {
static int[][] dr = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
static int N;
static ArrayList<FireBall>[][] map;
static Deque<Pos> ballList = new ArrayDeque<>();
public static void main(String[] args) throws IOException {
/**
* 중략
*/
int ballNum = Integer.parseInt(st.nextToken());
int commandNum = Integer.parseInt(st.nextToken());
for (int i = 0; i < ballNum; i++) {
/**
* 중략
*/
ballList.add(new Pos(r, c, new FireBall(r, c, m, d, speed)));
}
for (int command = 0; command < commandNum; command++) {
//이동
for (Pos pos : ballList) {
int d = pos.getBall().getD();
int speed = pos.getBall().getSpeed();
int newR = pos.getR() + dr[d][0] * speed;
if (newR == 0 || newR % N == 0) {
newR = N;
} else if (newR < 0) {
newR = newR % N + N;
} else {
newR = newR % N;
}
int newC = pos.getC() + dr[d][1] * speed;
/**
* 중략
*/
map[newR][newC].add(new FireBall(newR, newC, pos.getBall().getM(), d, speed));
}
ballList = new ArrayDeque<>();
//합치기
for (int r = 1; r <= N; r++) {
for (int c = 1; c <= N; c++) {
if (map[r][c].size() > 1) {
int even = 0;
int odd = 0;
int M = 0;
int speed = 0;
for (FireBall ball : map[r][c]) {
M += ball.getM();
speed += ball.getSpeed();
int d = ball.getD() % 2;
if(d ==0) {
even++;
}else {
odd++;
}
}
if (M / 5 > 0) {
if (even*odd == 0) { //방향 같음
/**
* 중략
*/
} else { //질량 0이면 사라짐
map[r][c] = new ArrayList<>();
}
map[r][c] = new ArrayList<>();
} else if (map[r][c].size() == 1) {
ballList.add(new Pos(r, c, map[r][c].get(0)));
map[r][c].remove(0);
}
}
}
} //명령 끝
/**
* 중략
*/
}
}아니......`map[newR][newC].add(new FireBall(newR, newC, pos.getBall().getM(), d, speed));` 이런 식의 코드를 짰는데 왜...? 구현 방식은 거의 똑같고 크게 차이 나는 게 없는데 왜??? 아무리 봐도 지금 코드가 나아 보이는데 어떻게 이런 일이!라는 생각에... Gemini(제미나이)에게 물어봤음.
그래서 예전 코드를 다시 제출했는데 그럼에도 너무 의미있는 차이가 나옴. 제미나이를 닦달하기 시작. 온갖 원인을 들고 알려주는데 반영하고 수정할수록 메모리가 점점 더 증가... 3배가 됐다가 다시 줄었다 늘었다... 처음 내 코드가 제일 적게 나오고... 갑자기 제미나이가 답을 찾기를 포기
제미나이를 호통치기 시작... 너 제미나이 프로잖어 인마!ㅜ
그래서 GPT 찾아갔는데 역시나 같은 소리
또 메모리 차이의 원인을 알려달라 호통치니? `Fireball`클래스에서 `dirs`를 `static`으로 하지 않았던 문제...ㅋㅋㅋㅋㅋㅋㅋ쿠ㅜㅜㅜㅜㅜㅜ 하 코딩은 GPT가 더 잘한다는 것을 배웠고... static 하나 때문에 시간을 얼마나....!!!!ㅜㅜㅜㅜㅜ 제미나이... 원하는 답은 잘 주고 gem도 훌륭한데 코딩은 지피티가 잘하는 거 같다..ㅜㅜㅜㅜ
상어 문제 포스팅 리스트
1. 아기 상어 (https://www.acmicpc.net/problem/16236)
2025.05.25 - [알고리즘/문제풀이] - [백준/BOJ] 16236 아기 상어 - JAVA
[백준/BOJ] 16236 아기 상어 - JAVA
[백준/BOJ] 16236 아기 상어 - JAVA문제https://www.acmicpc.net/problem/16236 문제 분석조건NxN 공간에 물고기와 아기 상어가 있다.상어는 자신보다 크기가 작은 물고기만 먹을 수 있고,크기가 같은 물고기는
ng-log.tistory.com
2. 청소년 상어 (https://www.acmicpc.net/problem/19236)
2025.06.08 - [알고리즘/문제풀이] - [백준/BOJ] 19236 청소년 상어 - JAVA
[백준/BOJ] 19236 청소년 상어 - JAVA
[백준/BOJ] 19236 청소년 상어 - JAVA문제https://www.acmicpc.net/problem/19236문제 분석조건4×4 크기의 공간이 1×1 크기의 정사각형으로 나누어져 있다. 각 칸에는 물고기가 한 마리씩 존재하며 각 물고기는 1
ng-log.tistory.com
3. 어른 상어 (https://www.acmicpc.net/problem/19237)
2025.06.11 - [알고리즘/문제풀이] - [백준/BOJ] 19237 어른 상어 - JAVA
[백준/BOJ] 19237 어른 상어 - JAVA
[백준/BOJ] 19237 어른 상어 - JAVA문제https://www.acmicpc.net/problem/19237문제 분석조건`N×N`격자 중 M개의 칸에 상어가 한 마리씩 들어있다. 상어는 시작 위치에 냄새를 뿌린다. 모든 상어는 1초마다 상하좌
ng-log.tistory.com