- 소요시간 : 1시간 5분
- 문제 사이트 : 백준
- 문제 수준 : 골드 4
- 문제 유형 : 구현, 시뮬레이션
- 다른 사람의 풀이를 참고 했는가 ? : X
- 문제 링크 : https://www.acmicpc.net/problem/20056
- 푼 날짜 : 2023.05.04
1. 사용한 자료구조 & 알고리즘
구현, 시뮬레이션, 큐
2. 사고과정
-> 파이어볼을 1칸씩 이동시킬 것인가?
전에 낚시왕 ( https://www.acmicpc.net/problem/17143) 문제에 크게 한번 데인적이 있어서 1칸씩 이동시키면 시간초과가 나나 먼저 계산해봤다.
속도가 최대 1000, 파이어볼의 개수가 최대 2500개, 최대 1000초 이므로
1칸씩 이동시키면 1000 x 1000 x 2500 으로 O(25억) 이 나온다.
우리는 속도 1000을 O(1)로 바꿀 수 있는 나머지 연산을 이용해야 한다. 그렇다면 O(250만) 까지 줄일 수 있다.
당시 낚시왕 문제를 풀었던 것은 https://velog.io/@anwlro0212/백준-17143-낚시왕-JAVA 여기에 있다.
-> 파이어볼의 방향이 모두 홀수/짝수인 것을 어떻게 구분?
그리고 다음으로 고민한 것은 다른 것은 비교적 쉬웠는데, 파이어볼의 방향이 모두 홀수이거나 모두 짝수인 것을 어떻게 구분하냐는 것이다. 처음에 문제를 잘못읽어서 파이어볼의 방향의 합이 짝수/홀수 인것을 구분하는 것으로 이해하고 문제를 풀었었는데, 1번 틀리고 원인을 찾다가 설계를 잘못했음을 느꼈다. 그래서 고민을 하던 중 queue를 이용하면 어떨까 생각했다.
2차원 queue를 만들어서 해당 좌표에 들어오는 방향을 모두 저장한 후 ,나중에 파이어볼의 합치고 나눌 때 해당 좌표의 queue에 저장된 파이어볼을 모두 꺼내서 짝수, 홀수를 모두 찾는다면 1,3,5,7 , 그게 아니라면 0,2,4,6 으로 조정하는 식으로 이를 해결했다.
-> 질량이 0인 파이어볼은 소멸되어 없어진다. 를 어떻게 처리할 것인가?
파이어볼의 위치를 조정해주는 메소드에서 아예 질량이 0인 경우에는 add시켜주지 않았다. add 시켜 놓고 나중에 파이어볼의 개수가 0인 것을 따로 지우는 것은 비효율적이라고 생각했다.
3. 풀이과정
- 맵에는 파이어볼의 개수의 합, 파이어볼의 합계질량, 파이어볼의 합계속도. queue에는 r,c,m,s,d 를 저장
- 파이어볼을 이동시키는데, 이때 다음 위치를 나머지 연산을 통해서 구함.
- 파이어볼의 위치를 조정시킨다. 주어진 조건에 따라 수행. 이때 이전에 구해 놓은 해당 좌표의 방향 값의 짝수, 홀수에따라 파이어볼이 4개로 나누어지는 작업에서 방향 결정.
- k번 반복했다면 모든 좌표의 질량의 합계를 구한다.
4. 소스코드
import java.util.*;
import java.io.*;
public class Main{
static int map[][][];
static Queue<Integer[]> fireball =new LinkedList<>();
static int dy[] = {-1,-1,0,1,1,1,0,-1};
static int dx[] = {0,1,1,1,0,-1,-1,-1};
static Queue<Integer> direction[][];
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
st=new StringTokenizer(br.readLine());
int N=Integer.parseInt(st.nextToken());
int M=Integer.parseInt(st.nextToken());
int K=Integer.parseInt(st.nextToken());
//맵에 3가지 정보를 담는다. 파이어볼의 개수, 파이어볼의 합계질량, 파이어볼의 합계속도
map = new int[N][N][3];
//해당 위치의 방향의 짝수, 홀수 여부를 알기 위함
direction=new LinkedList[N][N];
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
direction[i][j]=new LinkedList<>();
}
}
//파이어볼의 정보를 queue에 담는다.
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());
fireball.add(new Integer[] {r-1,c-1,m,s,d});
}
//파이어볼을 이동시키고
//파이어볼의 위치를 조정한다.
for(int i=0;i<K;i++) {
moveFireball();
replaceFireball();
}
//k번 함수가 시행되면 파이어볼의 개수를 세어준다
int sum = countFireball();
//합계 출력
System.out.println(sum);
}
//파이어볼을 이동시키는 함수
public static void moveFireball() {
while(!fireball.isEmpty()) {
Integer temp[]= fireball.poll();
int r = temp[0];
int c = temp[1];
int m = temp[2];
int s = temp[3];
int d = temp[4];
//1칸씩 이동시키지 않고, 나머지 연산으로 다음 위치를 구한다.
//(1칸씩 이동시킨다면 시간 초과가 날 것으로 예상)
r += (dy[d] * s);
c += (dx[d] * s);
r%=map.length;
c%=map.length;
//다음 위치가 음수가 된 경우는 따로 처리
if(r<0) {
r = Math.abs(r);
r = map.length - r;
}
if(c<0) {
c=Math.abs(c);
c=map.length - c;
}
map[r][c][0] += 1; //개수
map[r][c][1] += m; //질량
map[r][c][2] += s; //속도
//방향을 저장해준다.
direction[r][c].add(d);
}
}
//파이어볼의 위치 조정
public static void replaceFireball() {
for(int i=0;i<map.length;i++) {
for(int j=0;j<map.length;j++) {
int sum = map[i][j][0]; //파이어볼 개수
int m = map[i][j][1]; //파이어볼 합계 질량
int s = map[i][j][2]; //파이어볼 합계 속력
//해당 위치에 파이어볼이 1개라면 그냥 다시 똑같이 add해준다.
if(map[i][j][0]==1) {
int now = direction[i][j].poll();
fireball.add(new Integer[] {i,j,m,s,now});
}
//해당 위치에 파이어볼이 2개 이상이라면
else if(map[i][j][0]>1) {
//새로운 크기, 속도
int newM = m / 5;
int newS= s / sum ;
//기본 방향은 0,2,4,6
int dir[]= {0,2,4,6};
boolean findOdd= false;
boolean findEven=false;
//해당 좌표에 저장된 방향을 전부 poll해준다.
while(!direction[i][j].isEmpty()) {
int poll=direction[i][j].poll();
if(poll%2==0) findEven = true;
else findOdd = true;
}
//홀수도 찾고, 짝수도 찾았다면 1,3,5,7로 조정
if(findOdd==true&&findEven==true) {
dir[0] = 1;
dir[1] = 3;
dir[2] = 5;
dir[3] = 7;
}
//만약 새로운 합계가 0이라면 추가해주지 않아도 된다.
//그러므로 1이상인 경우에만 추가해준다.
if(newM!= 0) {
for(int k=0;k<4;k++) {
fireball.add(new Integer[] {i,j,newM,newS,dir[k]});
}
}
}
//해당 맵의 파이어볼을 없애준다.
map[i][j][0] = 0;
map[i][j][1] = 0;
map[i][j][2] = 0;
}
}
}
//파이어볼을 세어주는 함수
public static int countFireball() {
int sum = 0;
///temp[2]가 질량이므로 질량을 다 더해준다.
while(!fireball.isEmpty()) {
Integer temp[]= fireball.poll();
sum += temp[2];
}
return sum;
}
}
5. 결과
1344ms 는 해당 좌표의 짝수, 홀수의 개수를 구할 때 String 형의 HashMap을 통해서 처음에 구현했었음.
정답이 된 후 이것이 비효율적이라고 생각해서 2차원 queue로 대체했고 그 결과 488ms 를 받음.
6. 회고
구현, 시뮬레이션 문제를 많이 풀다보니 확실히 걸리는 시간이 줄었다.
이전과 비슷한 유형이라 익숙해지는 것 같다.
+) 이 포스팅은 velog 100번째 포스팅 !
하루에 백준 1문제 이상 푸는 것을 목표로 하고있다.
https://solved.ac/profile/anwlro0212
