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

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

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

 

1. 서론

 

이건... 골드4로 끝날 문제가 아니다. 구현 내용 자체는 간단한데 설명 부족 + 배열 이동하고 범위 체크해주는 게 진짜 까다로웠다.

(진짜 논리는 맞는데 이 범위 문제로 며칠을 전쟁함.)

 

+ 이와 유사한 문제 더 풀어보고 싶은 사람들은 이 문제들을 풀어볼 것.

 

SWEA 2382 미생물 격리

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl 

SW Expert Academy

Codetree 코드트리 싸움땅

https://www.codetree.ai/frequent-problems/battle-ground/description

코드트리

 

2. 문제 풀이

 

NxN 범위의 배열이 있다. 그 위에서 파이어볼 M개가 발사된다.
1번부터 n번과 연결되어 있고, 1번 열은 n번 열과 연결되어있다.

=> 이게 무슨 말인가 했더니 n번을 넘어가면 다시 1번으로 가게 된다는 소리였다^^

1. 모든 파이어볼이 자신의 방향 d로 속력 s칸만큼 이동
(이동하는 중에는 같은 칸에 여러 개의 파이어볼이 있을 수 있음)

=> 이것도 잠시 머무른다는 뜻인 건가 했더니 말 그대로 한 좌표에 여러 파이어볼이 존재할 수도 있다는 뜻이다

바뀌는 좌표 = 원래 좌표 + dx[d] * (속력 % n)
=> 벽 만나면 벽까지 가니까 % n

2. 이동이 모두 끝난 후 2개 이상의 파이어볼이 있는 칸
2-1. 같은 칸에 있는 파이어볼은 모두 하나로 합침
2-2. 파이어볼은 4개의 파이어볼로 나누어짐 (그 좌표 그대로)
2-3. 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다
질량: 합쳐진 파이어볼 질량의 합 / 5
속력: 합쳐진 파이어볼 속력의 합 / 합쳐진 파이어볼 개수
방향: 합쳐지는 파이어볼의 방향이 모두 홀수거나 짝수라면? 방향 0,2,4,6 아니면 1,3,5,7
질량이 0인 파이어볼은 소멸

K번 명령 후 남아있는 파이어볼의 질량의 합은?

파이어 볼은 8방으로 이동 
0: -1, 0
1: -1, 1
2: 0, 1
3: 1, 1
4: 1, 0
5: 1, -1
6: 0, -1
7: -1, -1

dx = {-1, -1, 0, 1, 1, 1, 0, -1}, dy = {0, 1, 1, 1, 0, -1, -1, -1}  //0~7

 

나는 이 로직을 그대로 따라서 문제를 풀었다.

 

문제를 읽다 보면 이해가 가지만 map을 만들어서 따로 움직일 필요가 없는 문제이기 때문에 그냥 좌표 리스트들만 관리해주면 된다.

그러기 위해서 나는 좌표값과 질량, 속력, 방향을 하나로 가지고 있을 수 있는 클래스를 만들었다.

그리고 입력받은 좌표들을 규칙대로 이동시키고 난 후 이 배열을 정렬해준다.

정렬해주는 이유는 좌표가 같은 것들을 한 곳에 모아서 처리하기 위해서다. (정렬을 안 하면 같은 좌표값을 찾기가 어려움)

그리고 난 후 좌표값이 같은 동안에 질량, 속력의 합을 구하고 짝수인지 홀수인지 체크해줬다.

그리고 다른 좌표가 나오면 계산을 멈추고 질량 / 5 로 좌표가 같은 것들의 질량을 계산해주는데 나는 이게 0이면 겹치는 것들의 값만 제거하고 넘어가서 질량이 0인 경우가 없게 만들었다.

0이 아닌 경우에는 4개로 나눠서 각자 방향을 가진 값들을 배열에 저장하고 기존에 있던 겹치는 좌표값들을 제거해줬다.

 

그리고 나는 제출하자마자 테케는 다 맞았는데 0%인 상태로 '틀렸습니다'가 나왔다.

구글을 뒤지자 위에 적은 로직 자체가 틀리지는 않았다.

그리고 반례를 통해 어디서 문제가 생겼는지 깨달았다.^^

 

다른 사람의 경우: 파이어볼의 질량이 0인 경우 처리 안 해줘서, 짝수, 홀수를 파이어볼 별로 처리 안 하고 더해서 짝수, 홀수 이렇게 구해서.

 

나는 이런 경우에 해당이 안 됐다. 내가 실마리를 찾게 된 반례 두 개.

 

4 4 2
1 2 13 4 3
1 4 12 3 7
4 1 2 5 7
4 2 6 3 0

 

답: 25

 

4 9 5
3 2 8 5 2
3 3 19 3 4
3 1 7 1 1
4 4 6 4 0
2 1 6 2 5
4 3 9 4 3
2 2 16 1 2
4 2 17 5 3
3 4 3 5 7

 

답: 33

 

나의 경우 문제가 좌표를 두 개씩 봐서 문제였다. 만약 좌표값이 같은 게 짝수 단위라면 문제가 없지만 좌표값이 홀수 단위로 같다면 당연히 코드가 엉망이 된다. 근데 문제는 두 개씩 보고 넘겨도 주어진 테케 + 웬만한 테케는 다 통과하게 된다는 것이다. 진짜 무서운 문제인 듯;

그래서 파이어볼 4개는 잘 만드는데 원래 있던 값을 지우는 부분에서 문제가 생겨서 답이 죄다 틀리게 되었다.

 

3. 코드 설명

 

import java.io.*;
import java.util.*;

public class Main {
	
	static int n;
	static List<Ball> list; //파이어볼 저장
	static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1}, dy = {0, 1, 1, 1, 0, -1, -1, -1}; //0~7
	
	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());
		int t = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		
		list = new ArrayList<>();
		
		for (int i = 0; i < t; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			list.add(new Ball(x, y, m, s, d));
		}
		
		for (int q = 0; q < k; q++) {
			move(); //1. 이동
			Collections.sort(list);
			calc(); //2. 파이어볼 계산
		}
		
		int sum = 0;
		for (int i = 0; i < list.size(); i++)
			sum += list.get(i).m;
		
		System.out.println(sum);
	}
	
	public static void calc() {
		List<Ball> tmp = new ArrayList<>(); //4개로 나눠지는 값 임시저장
		int i = 0;
		
		while(true) {
			if (i + 1 >= list.size()) break;
			//같은 칸에 있지 않은 경우 값 설정
			int mm = list.get(i).m, ms = list.get(i).s, cnt = 1, odd = 0, even = 0, start = i, nx = list.get(i).x, ny = list.get(i).y;
			if (list.get(i).d % 2 == 0)
				even++;
			else
				odd++;
			i++;
			
			if (nx == list.get(i).x && ny == list.get(i).y) { //같은 칸에 있는 경우
				while (true) {
					//하나로 합침
					mm += list.get(i).m;
					ms += list.get(i).s;
					cnt++;
					
					if (list.get(i).d % 2 == 0)
						even++;
					else
						odd++;
					nx = list.get(i).x; ny = list.get(i).y;
					i++;
					
					if (i >= list.size() || list.get(i).x != nx || list.get(i).y != ny) {//같은 칸이 끝난 경우
						int tm = mm / 5, ts = ms/cnt;
						if (tm != 0) {//4개로 나눔
							if (even == cnt || odd == cnt) {
								for (int j = 0; j < 8; j++)
									if (j % 2 == 0)
										tmp.add(new Ball(nx, ny, tm, ts, j));
							}
							else {
								for (int j = 0; j < 8; j++)
									if (j % 2 != 0)
										tmp.add(new Ball(nx, ny, tm, ts, j));
							}
						}
						for (int j = start; j < start + cnt; j++)
							list.remove(start);//원래 값 제거
						i -= cnt;
						break;
					}	
				}
			}
		}
		
		list.addAll(tmp); //4개로 나눈값 원래 배열에 추가
	}
	
	public static void move() { //파이어볼 이동
		for(int i = 0; i < list.size(); i++) {
			int x = list.get(i).x + dx[list.get(i).d] * (list.get(i).s % n);
			int y = list.get(i).y + dy[list.get(i).d] * (list.get(i).s % n);
			//범위 벗어나는거 처리
			if (x > n) x -= n;
			else if (x < 1) x += n;
			if (y > n) y -= n;
			else if (y < 1) y += n;

		    list.set(i, new Ball(x, y, list.get(i).m, list.get(i).s, list.get(i).d));
		}
	}
}

class Ball implements Comparable<Ball>{
	int x, y, m, s, d; //좌표, 질량, 속력, 방향
	
	public Ball(int x, int y, int m, int s, int d) {
		this.x = x;
		this.y = y;
		this.m = m;
		this.s = s;
		this.d = d;
	}
	
	@Override
	public int compareTo(Ball o) { //좌표순으로 정렬
		if (this.x == o.x)
			return this.y - o.y;
		return this.x - o.x;
	}
}

 

최대한 심플하게 코드를 짜려고 했는데 이렇게 되어버렸다.

좌표 순으로 정렬이 필요하고 Type을 새로 선언해서 만들었기 때문에 Comparable로 정렬 조건을 설정해줬다.

파이어볼이 이동할 때는 범위를 넘어도 값을 순환하기 때문에 속력을 %n 해주고 범위 넘은 것들은 +-n을 해줘서 범위를 조절했다.(set)

그리고 while문을 돌면서 list를 도는데 연속으로 같은 좌표가 나오기 전까지는 현재 위치의 값들을 다음 위치의 탐색을 위해 값을 세팅해줬다. 그리고 현재 값을 기준으로 전의 값과 좌표가 같으면 질량, 속력, 방향을 계속 체크했고 다른 값이 나오면 그때 앞에서 체크했던 것들을 계산해주는 방식으로 처리했다. 그리고 4개로 나눠서 배열에 넣은 후에는 원래 겹쳤던 값들을 제거해줬다. (remove) 이 작업을 동시에 이루면 배열작업에 문제가 생길까 봐 따로 tmp에 4개를 저장해주고 원래의 배열에서 값을 제거해주고 나중에 그 둘을 합쳤다(addAll()).