Algorithm/Problem
마법사 상어와 파이어볼(BJ_G4_20056)
당진개발자
2024. 2. 24. 15:52
1. 문제 링크
https://www.acmicpc.net/problem/20056
20056번: 마법사 상어와 파이어볼
첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치
www.acmicpc.net
2. 나의 코드
메모리: 40540kb
시간: 732ms
코드 길이: 4868B
시간 복잡도 : O(KM)
설명
- 먼저 모든 파이어볼을 이동시킨 후 합치기
- 합치는 과정에서 다음 객체와 같은지 다른지 비교
- 시작과 끝 인덱스를 사용하여 같은 위치에 있는 것들은 인덱스 리스트에 추가(끝나면 삭제)
- 추가해야 할 객체도 리스트에 추가 후 한번에 추가import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static class FireBall implements Comparable<FireBall> {
int r, c, m, s, d;
public 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;
}
@Override
public int compareTo(FireBall o) {
if (this.r != o.r)
return this.r - o.r;
return this.c - o.c;
}
}
static int[] dr = {-1, -1, 0, 1, 1, 1, 0, -1};
static int[] dc = {0, 1, 1, 1, 0, -1, -1, -1};
static int N, M, K;
static List<FireBall> fireBalls;
public static void main(String[] args) throws IOException {
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());
fireBalls = new ArrayList<FireBall>();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
fireBalls.add(new FireBall(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken())));
}
while (K-- > 0) {
move();
fireBalls.removeIf(f -> f.m <= 0);
}
int result = 0;
for (FireBall f : fireBalls) {
result += f.m;
}
System.out.println(result);
}
// 이동
private static void move() {
for (FireBall fireBall : fireBalls) {
int tempR = (fireBall.r + N + dr[fireBall.d] * (fireBall.s % N)) % N;
int tempC = (fireBall.c + N + dc[fireBall.d] * (fireBall.s % N)) % N;
fireBall.r = tempR;
fireBall.c = tempC;
}
// 같은 위치 합치기
union();
}
private static void union() {
int unionCnt = 1;
int s = 0, e = 0;
List<FireBall> addFireBallList = new ArrayList<>(); // 추가할 파이어볼 객체
List<Integer> removedIdxList = new ArrayList<>(); // 삭제할 인덱스
Collections.sort(fireBalls);
for (int i = 0; i < fireBalls.size() - 1; i++) {
FireBall now = fireBalls.get(i);
FireBall next = fireBalls.get(i + 1);
// 다음거랑 같으면?
if (now.r == next.r && now.c == next.c) {
next.m += now.m;
next.s += now.s;
unionCnt++;
e = i + 1; // 다음거랑 같으면 인덱스 증가
removedIdxList.add(i);
if (i == fireBalls.size() - 2) {
removedIdxList.add(i + 1);
int newM = next.m / 5;
int newS = next.s / unionCnt;
int newD;
if (EvenAddCheck(s, e)) newD = 0;
else newD = 1;
for (int j = 0; j < 4; j++) {
addFireBallList.add(new FireBall(now.r, now.c, newM, newS, newD));
newD += 2;
}
}
} else { // 다음거랑 다르면?
if (unionCnt > 1) {
int newM = now.m / 5;
int newS = now.s / unionCnt;
int newD;
if (EvenAddCheck(s, e)) newD = 0;
else newD = 1;
for (int j = 0; j < 4; j++) {
addFireBallList.add(new FireBall(now.r, now.c, newM, newS, newD));
newD += 2;
}
removedIdxList.add(i);
}
s = i + 1;
unionCnt = 1;
}
}
int cnt = 0;
for (int idx : removedIdxList) {
fireBalls.remove(idx - cnt++);
}
fireBalls.addAll(addFireBallList);
}
// 삭제할 것들이 모두 홀수인지 짝수인지 확인
private static boolean EvenAddCheck(int s, int e) {
int odd = 0;
int even = 0;
for (int i = s; i <= e; i++) {
if (fireBalls.get(i).d % 2 == 0) even++;
else odd++;
}
if (odd == 0 || even == 0) return true;
return false;
}
}
3. 정답 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
static int N, M, K;
static int[] dr = {-1, -1, 0, 1, 1, 1, 0, -1};
static int[] dc = {0, 1, 1, 1, 0, -1, -1, -1};
static ArrayList<Fireball> fireballs;
static class Fireball implements Comparable<Fireball> {
int r, c, m, d, s, num; // num은 2차원 배열의 몇번째 칸인지를 의미함
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;
}
@Override
public int compareTo(Fireball o) {
return this.num - o.num;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
// 초기 세팅
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
fireballs = new ArrayList<>();
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());
fireballs.add(new Fireball(r, c, m, d, s));
}
play();
int answer = 0;
for (Fireball fb : fireballs) {
answer += fb.m;
}
System.out.println(answer);
}
private static void play() {
// K번동안 반복
for (int time = 0; time < K; time++) {
for (int i = 0; i < fireballs.size(); i++) {
Fireball now = fireballs.get(i);
// 속력 s만큼 방향 d로 이동
int nr = now.r + dr[now.d] * (now.s % N);
int nc = now.c + dc[now.d] * (now.s % N);
if (nr > 0) {
nr %= N;
} else if (nr < 0) {
nr += N;
}
if (nc > 0) {
nc %= N;
} else if (nc < 0) {
nc += N;
}
now.r = nr;
now.c = nc;
now.num = nr * N + nc;
}
// 위치순으로 파이어볼 정렬
Collections.sort(fireballs);
for (int i = 0; i < fireballs.size() - 1; i++) {
Fireball now = fireballs.get(i);
Fireball next = fireballs.get(i + 1);
// 2개 이상의 파이어볼이 있는 칸을 찾은 경우
if (now.num == next.num) {
int num = now.num;
boolean oddFlag = false;
boolean evenFlag = false;
int mSum = 0;
int sSum = 0;
int cnt = 0;
// 같은 칸에 있는 파이어볼들을 찾아서 로직을 수행
while (i < fireballs.size() && num == fireballs.get(i).num) {
Fireball fb = fireballs.get(i);
mSum += fb.m;
sSum += fb.s;
if (fb.d % 2 == 0) {
evenFlag = true;
} else {
oddFlag = true;
}
fireballs.remove(i);
cnt++;
}
mSum /= 5;
sSum /= cnt;
// 질량이 1이상이라면
if (mSum > 0) {
// 합쳐지는 파이어볼의 방향이 모두 홀수이거나 짝수이면
if (!oddFlag || !evenFlag) {
for (int j = 0; j < 7; j += 2) {
fireballs.add(i, new Fireball(num / N, num % N, mSum, j, sSum));
}
// 그렇지 않다면
} else {
for (int j = 1; j < 8; j += 2) {
fireballs.add(i, new Fireball(num / N, num % N, mSum, j, sSum));
}
}
i += 3;
// 질량이 0이라면 파이어볼이 사라지므로 기존 index를 다시 탐색해야함
} else {
i--;
}
}
}
}
}
}import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
static int N, M, K;
static int[] dr = {-1, -1, 0, 1, 1, 1, 0, -1};
static int[] dc = {0, 1, 1, 1, 0, -1, -1, -1};
static ArrayList<Fireball> fireballs;
static class Fireball implements Comparable<Fireball> {
int r, c, m, d, s, num; // num은 2차원 배열의 몇번째 칸인지를 의미함
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;
}
@Override
public int compareTo(Fireball o) {
return this.num - o.num;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
// 초기 세팅
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
fireballs = new ArrayList<>();
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());
fireballs.add(new Fireball(r, c, m, d, s));
}
play();
int answer = 0;
for (Fireball fb : fireballs) {
answer += fb.m;
}
System.out.println(answer);
}
private static void play() {
// K번동안 반복
for (int time = 0; time < K; time++) {
for (int i = 0; i < fireballs.size(); i++) {
Fireball now = fireballs.get(i);
// 속력 s만큼 방향 d로 이동
int nr = now.r + dr[now.d] * (now.s % N);
int nc = now.c + dc[now.d] * (now.s % N);
if (nr > 0) {
nr %= N;
} else if (nr < 0) {
nr += N;
}
if (nc > 0) {
nc %= N;
} else if (nc < 0) {
nc += N;
}
now.r = nr;
now.c = nc;
now.num = nr * N + nc;
}
// 위치순으로 파이어볼 정렬
Collections.sort(fireballs);
for (int i = 0; i < fireballs.size() - 1; i++) {
Fireball now = fireballs.get(i);
Fireball next = fireballs.get(i + 1);
// 2개 이상의 파이어볼이 있는 칸을 찾은 경우
if (now.num == next.num) {
int num = now.num;
boolean oddFlag = false;
boolean evenFlag = false;
int mSum = 0;
int sSum = 0;
int cnt = 0;
// 같은 칸에 있는 파이어볼들을 찾아서 로직을 수행
while (i < fireballs.size() && num == fireballs.get(i).num) {
Fireball fb = fireballs.get(i);
mSum += fb.m;
sSum += fb.s;
if (fb.d % 2 == 0) {
evenFlag = true;
} else {
oddFlag = true;
}
fireballs.remove(i);
cnt++;
}
mSum /= 5;
sSum /= cnt;
// 질량이 1이상이라면
if (mSum > 0) {
// 합쳐지는 파이어볼의 방향이 모두 홀수이거나 짝수이면
if (!oddFlag || !evenFlag) {
for (int j = 0; j < 7; j += 2) {
fireballs.add(i, new Fireball(num / N, num % N, mSum, j, sSum));
}
// 그렇지 않다면
} else {
for (int j = 1; j < 8; j += 2) {
fireballs.add(i, new Fireball(num / N, num % N, mSum, j, sSum));
}
}
i += 3;
// 질량이 0이라면 파이어볼이 사라지므로 기존 index를 다시 탐색해야함
} else {
i--;
}
}
}
}
}
}
4. 배운 점
- 이동을 처리하는 부분에서 많은 고생을 했다.
- 리스트를 사용할 경우 Stream을 많이 사용해보자!