[JAVA] [BOJ] 17143. 낚시왕

음 이전의 미생물 격리를 풀고난 뒤 바로 풀었기 때문에 똑같은 조건에서 풀었는데 생각보다 효율이 좋지 않았다.

 

이러한 방법이 있다는 것을 참고만 하고 보시는 것을 추천드립니다.

 

1. 낚시꾼은 결국 j가 0일때 부터 j가 c-1일때 까지 잡는다

2. 상어 친구들이 움직인다. 정지한 좌표가 같을 경우 크기가 큰 상어가 작은 상어를 잡아 먹는다. ( 보통 상어가 커지게 하는 데 이 문제의 경우 상어의 크기는 항상 유지 된다.)

3. HashSet을 이용하여 잡아먹힌 상어를 제외하고 다시 list에 넣는다!

 

이 문제가 살짝 어려운 경우 이전 포스트인 미생물 격리를 한번 보고 온다면 이 설명이 더 편하게 이해가 갈 것이다.

예전과 다르게 왜 Queue가 아닌 list를 썼느냐고 물어본다면 예전에는 움직이고 서로 잡아먹는 것이 끝이었다면 지금은 낚시꾼이 잡는 것도 포함되어 list를 사용하였고 이를 clear 해주는 것에 시간이 조금 걸린 것 같다.

 

Arrays.fill을 조금 더 편하게 쓰기 위해 [i][j] 를 i * c + j 로 나타내었는데 이것 또한 저는 많이 쓰기도 하고 이해가 가지 않을 경우 본인이 종이에 각 좌표를 써놓고 0,0 은 0 / 0,1 은 1 이런 식으로 차례로 쓴다음 i 와 j 그리고 가로길이 c에 대해서 생각해본다면 더 알기 쉽다고 생각이 든다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.HashSet;

public class Main17143 {
	static class Shark{
		int i, j, speed, dir, size;
		public Shark(int i, int j, int speed, int dir, int size) {
			this.i = i;
			this.j = j;
			this.speed = speed;
			this.dir = dir;
			this.size = size;
		}
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String[] str = br.readLine().split(" ");
		int r = Integer.parseInt(str[0]);
		int c = Integer.parseInt(str[1]);
		int m = Integer.parseInt(str[2]);
		ArrayList<Shark> list = new ArrayList<Shark>();
		HashSet<Integer> hs = new HashSet<Integer>();
		int[] dx = {-1, 1, 1, -1};
		int di = 0;
		int dj = 0;
		int size = 0;
		int dir = 0;
		int speed = 0;
		int sumSize = 0;
		int[] sizeMap = new int[r*c];
		int[] dirMap = new int[r*c];
		int[] speedMap = new int[r*c];
		for(int i=0; i<m; ++i) {
			str = br.readLine().split(" ");
			di = Integer.parseInt(str[0])-1;
			dj = Integer.parseInt(str[1])-1;
			speed = Integer.parseInt(str[2]);
			dir = Integer.parseInt(str[3]);
			size = Integer.parseInt(str[4]);
			list.add(new Shark(di, dj, speed, dir, size));
		}
		int idx = 0;
		int minI = Integer.MAX_VALUE;
		Shark s = null;
		for(int j=0; j<c; ++j) {			
			hs.clear();
			idx = -1;
			minI = Integer.MAX_VALUE;
			
			for(int i=0; i<list.size(); ++i) {
				s = list.get(i);
				di = s.i;
				dj = s.j;
				speed = s.speed;
				dir = s.dir;
				size = s.size;
				if(dj == j && di < minI) {
					minI = di;
					idx = i;
				}
				//1. 위 / 2. 아래 / 3. 오른쪽 / 4. 왼쪽
				if(dir == 1) {
					for(int k=0; k<speed; ++k) {
						di += dx[dir-1];
						if(di < 0 ) {
							dir = 2;
							di = 1;
						}else if(di >= r) {
							dir = 1;
							di = r-2;
						}
					}
				}else if(dir == 2){
					for(int k=0; k<speed; ++k) {
						di += dx[dir-1];
						if(di < 0 ) {
							dir = 2;
							di = 1;
						}else if(di >= r) {
							dir = 1;
							di = r-2;
						}
					}
				}else if(dir == 3) {
					for(int k=0; k<speed; ++k) {
						dj += dx[dir-1];
						if(dj < 0 ) {
							dir = 3;
							dj = 1;
						}else if(dj >= c) {
							dir = 4;
							dj = c-2;
						}
					}
				}else if(dir == 4) {
					for(int k=0; k<speed; ++k) {
						dj += dx[dir-1];
						if(dj < 0 ) {
							dir = 3;
							dj = 1;
						}else if(dj >= c) {
							dir = 4;
							dj = c-2;
						}
					}
				}
				s.i = di;
				s.j = dj;
				s.dir = dir;
				
			}
			for(int i=0; i<list.size(); ++i) {
				if(i == idx) {
					sumSize += list.get(i).size;
					continue;
				}
				s = list.get(i);
				di = s.i;
				dj = s.j;
				speed = s.speed;
				dir = s.dir;
				size = s.size;
				if(sizeMap[di*c+dj] < size) {
					sizeMap[di*c+dj] = size;
					dirMap[di*c+dj] = dir;
					speedMap[di*c+dj] = speed;
				}
				hs.add(di*c+dj);
			}
			list.clear();
			for(int value : hs) {
				di = value/c;
				dj = value%c;
				list.add(new Shark(di, dj, speedMap[di*c+dj], dirMap[di*c+dj], sizeMap[di*c+dj]));
				speedMap[di*c+dj] = 0;
				dirMap[di*c+dj] = 0;
				sizeMap[di*c+dj] = 0;
			}
		}
		bw.write(""+sumSize);
		bw.close();
		br.close();
	}

}