[알고리즘] 백준20056 마법사 상어와 파이어볼 - 자바

https://www.acmicpc.net/problem/20056

20056번: 마법사 상어와 파이어볼

 

[풀이 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class BOJ_20056_마법사상어와파이어볼2 {
	static int N, M, K;
	static int[][][] map;
	static Queue<Point> q = new LinkedList<>();
	static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1};
	static int[] dx = {0, 1, 1, 1, 0, -1, -1, -1};
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = parse(st.nextToken());
		M = parse(st.nextToken());
		K = parse(st.nextToken());
		
		map = new int[N][N][6];
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int y = parse(st.nextToken())-1;
			int x = parse(st.nextToken())-1;
			int m = parse(st.nextToken()); // 질량
			int s = parse(st.nextToken()); // 속도
			int dir = parse(st.nextToken()); // 방향

			map[y][x][0]++;
			map[y][x][1] += m;
			map[y][x][2] += s;
			map[y][x][5] += dir;
			
			if(dir%2==0) map[y][x][3]++; // 짝수
			else map[y][x][4]++; // 홀수
			
			q.offer(new Point(y, x, m, s, dir));
		}
		
		while(K-- > 0) {
			move();
			divide();
		}
		resultPrint();
	}

	private static void resultPrint() {
		int ans = 0;
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				ans += map[i][j][1];
			}
		}
		System.out.println(ans);
	}

	private static void divide() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				if(map[i][j][0] >= 2) {
					fireDivide(i, j);
				}else if(map[i][j][0] == 1) {
					q.offer(new Point(i, j, map[i][j][1], map[i][j][2], map[i][j][5]));
				}
			}
		}
	}

	private static void fireDivide(int i, int j) {
		int size = map[i][j][0]; // 개수
		int mSum = map[i][j][1]/5; // 질량의 합
		int speadSum = map[i][j][2]/size; //속도의 합
		int even = map[i][j][3]; // 짝수
		int odd = map[i][j][4]; // 홀수
		
		if(mSum != 0) {		
			map[i][j][0] = 4;	
			map[i][j][1] = mSum * 4;
			map[i][j][2] = speadSum*4;
			map[i][j][5] = 0;
			
			for (int f = 0; f < 4; f++) {
                q.offer(new Point(i, j, mSum, speadSum, (f * 2 + ((even == size || odd == size) ? 0 : 1) )));
            }
            map[i][j][3] = (even == size || odd == size) ? 4 : 0;
            map[i][j][4] = 4 - map[i][j][3];
			
		}else {
			for(int k=0; k<=5; k++) { // 초기화
				map[i][j][k] = 0;
			}
		}
	}

	private static void move() {
		while(!q.isEmpty()) {
			Point point = q.poll();
			map[point.y][point.x][0]--;
			map[point.y][point.x][1] -= point.m;
			map[point.y][point.x][2] -= point.s;
			map[point.y][point.x][5] -= point.dir; 
			
			if(point.dir%2==0) map[point.y][point.x][3]--; // 짝수
			else map[point.y][point.x][4]--; // 홀수
			
			int y = (point.y + dy[point.dir]*point.s + N*1000)%N;
			int x = (point.x + dx[point.dir]*point.s + N*1000)%N;
			
			map[y][x][0]++;
			map[y][x][1] += point.m;
			map[y][x][2] += point.s;
			map[y][x][5] += point.dir;
			
			if(point.dir%2==0) map[y][x][3]++; // 짝수
			else map[y][x][4]++; // 홀수
			
		}
	}

	static class Point{
		int y, x, m, s, dir;
		
		Point(int y, int x, int m, int s, int dir){
			this.y = y;
			this.x = x;
			this.m = m;
			this.s = s;
			this.dir = dir;
		}
	}
	
	private static int parse(String s) {
		return Integer.parseInt(s);
	}
}

정말 힘들게 풀었던 문제.. 처음에는 큐만 활용하려고 하다 보니 반복문이 많아져서 시간 초과가 자꾸 나왔다. 그리고 문제에서 놓치는 부분이 없도록 잘 체크해야 한다.

 

[이 문제를 풀면서 부족하다고 느낀 점]

• 기본기? 가 부족했던 것 같다. 어떤 상황에 for문을 써야 할지 while문을 써야할지 잘 생각해야겠다. 내가 막혔던 부분 중 하나가 while(size-- > 0) 이렇게 size가 다 감소하면 while문을 빠져나오게 구현했는데 반복문을 나온 후에 다시 size로 뭘 하려고 하다가 자꾸 음수 값이 나와서 헤맸던 것 같다... 완전 바보 같은 실수..😂😂
  
  
• 두 번째는 위 코드에서 보면 (point.y + dy[point.dir]*point.s + N*1000)%N; 이렇게 모듈러 연산을 해준 부분이 있는데 처음에는 이렇게 간단한 방법이 있는 줄 모르고 직접 if문으로 파이어볼이 주어진 범위를 나갔을 경우를 처리해줬다. 여기서 1000을 곱한 이유는 1 ≤ si ≤ 1,000 속도의 최댓값이 1000이기 때문이다. 

 

[풀이 로직]

함수는 크게 아래처럼 3개로 구현했다.

1. move() : 파이어볼을 이동시킨다!
2. divide() : 2개 이상 모인 파이어볼은 fireDivde()함수로 이동하도록하고 불이 하나밖에 없다면 다시 큐에 담아준다.
   2-1. fireDivide() : 2개이상 모인 파이어볼을 문제에서 주어진대로 나눠준다!

위 로직을 문제에서 주어진 K만큼 반복하면 된다.

 

그리고 3차원 배열을 활용했다는 점도 문제를 푸는 데 있어 매우 중요했던 것 같다.

• 3차원 배열을 활용한 이유는 단순히 큐로만 풀려고 하면 반복문을 정말 많이 쓰게 된다. 
• map = new int [N][N][6]; 3차원 배열에 순서대로 파이 볼의 개수, 질량의 합, 속도의 합, 짝수 카운팅, 홀수 카운팅, 방향!
• 제일 헷갈렸던 건 방향을 담는 것인데 불이 하나만 담기는 경우만 신경 쓰면 된다. 두 개부터는 어차피 fireDivide함수에서 처리가 되기 때문에 전혀 신경을 안 써줘도 된다. 

 

이 문제를 풀 수 있도록 도와준 스터디원에게 정말 감사하다...👍👍