[BOJ 17143] 낚시왕 (Java)

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

17143번: 낚시왕

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_BOJ_17143 {
	static class Shark implements Comparable<Shark>{
		int r, c, s, d, z;
		public Shark(int r, int c, int s, int d, int z) {
			this.r = r;
			this.c = c;
			this.s = s;
			this.d = d;
			this.z = z;
		}
		@Override
		public int compareTo(Shark o) {
			return o.z-this.z;
		}
		
	}
	static int[] dr= {0,-1,1,0,0};
	static int[] dc= {0,0,0,1,-1};
	static int[] opposites= {0,2,1,4,3};
	static int R, C, M;
	static int answer=0;
	static Shark[][] map;
	static PriorityQueue<Shark> sharks;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		R=Integer.parseInt(st.nextToken());
		C=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		map=new Shark[R][C];
		int r,c,s,d,z;
		for (int i=0; i<M; i++) {
			st=new StringTokenizer(br.readLine());
			r=Integer.parseInt(st.nextToken())-1;
			c=Integer.parseInt(st.nextToken())-1;
			s=Integer.parseInt(st.nextToken());
			d=Integer.parseInt(st.nextToken());
			z=Integer.parseInt(st.nextToken());
			map[r][c]=new Shark(r,c,s,d,z);
		}
		for (int i=0; i<C; i++) {
			//fishing
			for (int j=0; j<R; j++) {
				if (map[j][i]!=null) {
					answer+=map[j][i].z;
					map[j][i]=null;
					break;
				}
			}
			//gather
			gather();
			//move
			move();
		}
		System.out.println(answer);
	}
	private static void move() {
		Shark[][] vMap=new Shark[R][C]; 
		while (!sharks.isEmpty()) {
			Shark shark=sharks.poll();
			int r=shark.r;
			int c=shark.c;
			int nd=shark.d;
			int nr=r+dr[nd];
			int nc=c+dc[nd];
			int cnt=0;
			while(cnt<shark.s) {
				if (isValid(nr,nc)) {
					cnt++;
				}
				else {
					nr-=dr[nd];
					nc-=dc[nd];
					nd=opposites[nd];
					shark.d=nd;
				}
				nr+=dr[nd];
				nc+=dc[nd];
			}
			nr-=dr[nd];
			nc-=dc[nd];
			if (vMap[nr][nc]==null) {
				vMap[nr][nc]=new Shark(nr, nc, shark.s, nd, shark.z);
			}
		}
		map=vMap;
		
	}
	private static void gather() {
		sharks=new PriorityQueue<>();
		for (int i=0; i<R; i++) {
			for (int j=0; j<C; j++) {
				if (map[i][j]!=null) {
					Shark sh=map[i][j];
					sharks.offer(new Shark(sh.r,sh.c,sh.s,sh.d,sh.z));
				}
			}
		}
	}
	private static boolean isValid(int r, int c) {
		return r>=0 && r<R && c>=0 && c<C;
	}

}

자료구조는 다음과 같이 정한다:

-각 위치에 있는 shark를 저장하는 Shark[][] map

-움직일 shark를 저장하는 PriorityQueue<Shark> pq; (사이즈가 큰 shark부터 먼저 튀어나오도록)

 

동작과정은 다음과 같다:

-현재 있는 열 위치에서 가장 가까운 행에 위치한 shark를 잡고, 해당 위치에 shark를 null 처리 해줘서 삭제 처리한다.

-gather() 함수를 호출해 현재 남아있는 shark를 탐색 대상을 모아두는 priority queue에 넣어준다.

-move() 함수를 호출해 shark를 움직인다. 

 -vMap이라고 움직인 후의 map을 저장하는 배열을 선언한다.

 -size가 큰 shark부터 조건에 맞게 움직여준다. 이때 움직일 때 경계를 벗어났는지 체크하고 그렇다면 방향을 반대로 돌려서 다시 움직이는 방식을 취한다.

-중복 체크는 만약 vMap에 shark가 존재할 경우, 이 경우는 무조건 넣으려고 하는 지금 shark보다 큰 size의 shark일 것이므로(큰 size의 shark부터 먼저 움직여 줬으므로) vMap에 넣어주지 않는다. (kill 처리)

-모든 상어가 다 움직였으면 vMap을 map으로 옮긴다.

 

코드를 짜면서, 만약 속력이 최대치가 나올 경우 시간초과가 나지 않을까? 했다. 일일히 움직여주는 방식은 계산해보니 10억정도가 나와서.. 다행히 통과를 했지만, 다른 분들의 코드를 보니 최적화 방법이 있었다.

https://yabmoons.tistory.com/288

만약 shark가 자기 위치로 돌아올려면 위,아래 방향일 경우 (R-1)*2 칸 움직여야 되고, 좌,우 방향일 경우 (C-1)*2칸 움직여야 된다. 그래서 속력 s가 그 칸들보다 같거나,크면 모듈러스 연산을 통해서 그 나머지만 움직여주면 된다!

자기 위치로 돌아올려면 몇 칸 거쳐야 하나? 속력이 그 칸 이상이면 어차피 자기 칸으로 다시 돌아오는 경우가 생기는 것이므로 그 칸수로 나눈 나머지정도로만 움직여주면 OK다!

 

또, 모든 상어들을 Shark Vector에 저장한 후, 죽은 상어는 -1 처리를 해줄 수 있다.

또 vector<int> map[][] 자료구조를 이용해, 해당 위치에 있는 상어들의 목록을 저장한다.

상어들을 움직이기 전에는 그 벡터들을 모두 clear 해줘서 새 맵을 만들 준비를 하고, Shark Vector에 있는 상어들을 하나씩 빼서 죽은 상어로 표시를 한 건 제외하고 움직여주고, 새 위치로 업데이트를 해주고 map의 그 위치에 상어를 넣어준다.

중복되는 상어의 처리는 각 map의 위치에 있는 상어 리스트를 정렬한 뒤 나머지 상어는 죽은 처리 해주고, 한개의 상어만 해당 map의 위치에 넣어준다.