[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.StringTokenizer;

public class Main_BOJ_17143 {
	static class Shark{
		int r, c, s, d, z;
		boolean isKilled;
		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;
			this.isKilled=false;
		}
	}
	static int[] dr= {0, -1, 1, 0, 0};
	static int[] dc= {0, 0, 0, 1, -1};
	static int R, C, M;
	static int[][] map;
	static Shark[] sharks;
	static int answer=0;
	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 int[R+1][C+1];
		sharks=new Shark[M+1];
		for (int i=1; i<=M; i++) {
			st=new StringTokenizer(br.readLine());
			int r=Integer.parseInt(st.nextToken());
			int c=Integer.parseInt(st.nextToken());
			int s=Integer.parseInt(st.nextToken());
			int d=Integer.parseInt(st.nextToken());
			int z=Integer.parseInt(st.nextToken());
			sharks[i]=new Shark(r,c,s,d,z);
			map[r][c]=i;
		}
		int fisher=1;
		while (fisher<C+1) {
			fishing(fisher); 
			move();
			rearrange();
/*			System.out.println("======");
			for (int i=1; i<=R; i++) {
				for (int j=1; j<=C; j++) {
					if (map[i][j]==0) System.out.print("0 ");
					else System.out.print(sharks[map[i][j]].z+" ");
				}
				System.out.println();
			}*/
			fisher++;
		}
		System.out.println(answer);

	}

	private static void fishing(int loc) {
		for (int i=1; i<=R; i++) {
			if (map[i][loc]!=0) {
				int shark_num=map[i][loc];
				answer+=sharks[shark_num].z;
				sharks[shark_num].isKilled=true;
				return;
			}
		}
	}
	private static void move() {
		int r, c, d, s, nr, nc, cnt;
		for (int i=1; i<=M; i++) {
			if (!sharks[i].isKilled) {
				r=sharks[i].r;
				c=sharks[i].c;
				d=sharks[i].d;		
				s=sharks[i].s;
				if (d==1 || d==2) {
					s%=((R-1)*2);
				}
				else if (d==3 || d==4) {
					s%=((C-1)*2);
				}
				nr=r;
				nc=c;
				cnt=0;
				while (cnt<s) {
					nr+=dr[d];
					nc+=dc[d];
					if (nr<=0 || nc<=0 || nr>R || nc>C) {
						nr-=dr[d];
						nc-=dc[d];
						d=d%2==0?d-1:d+1;
						continue;
					}
					cnt++;
				}
				sharks[i].r=nr;
				sharks[i].c=nc;
				sharks[i].d=d;	
			}
		}
	}
	
	private static void rearrange() {
		int[][] temp=new int[R+1][C+1];
		int r, c;
		for (int i=1; i<=M; i++) {
			if (!sharks[i].isKilled) {
				r=sharks[i].r;
				c=sharks[i].c;
				if (temp[r][c]!=0) {
					int size=sharks[temp[r][c]].z;
					if (size>sharks[i].z) {	//기존에 있는 상어가 클때
						sharks[i].isKilled=true;
					}
					else {
						sharks[temp[r][c]].isKilled=true;
						temp[r][c]=i;
					}
				}
				else {
					temp[r][c]=i;
				}
			}
		}
		map=temp;
	}

}

처음엔 상어를 s만큼 직접 다 움직이는 걸로 구현했으나.. AC는 받았지만 시간이 너무 오래걸려서 (1900ms..) 

움직이는 방법을 고민했다. 

 

좌,우로 움직이는 상어가 (C-1)*2번 움직일 경우,상, 하로 움직이는 상어가 (R-1)*2 번 움직일 경우 원래 제 자리로, 원래 제 방향으로 돌아오는 경우이다.

 

즉 s를 (C-1)*2나 (R-1)*2 만큼 나누어서 그 거리만큼만 움직여주면 된다. 

 

전체적으로 코드가 돌아가는 방식은 이렇다.

 

int[][] map : 각 위치에 저장된 상어의 번호를 저장

Shark[] sharks: 각 번호를 가진 상어의 위치, 크기, 속력, 방향, 죽음 여부 저장

 

1) fishing 함수: 현재 낚시꾼 위치에서 가장 가까운 상어를 잡는다. answer을 갱신해주고, 해당 shark를 죽음 처리 해준다.

2) move 함수: 상어를 움직여준다=>sharks 배열을 돌면서 아직 죽지 않은 상어에 대해 문제의 조건에 따라 움직인다.

이때 속력만큼 다 움직이지 말고, (R-1)*2, (C-1)*2 만큼 나누어줘서((R-1)*2, (C-1)*2 만큼 거리를 이동할 경우 현재 상어의 위치, 방향과 동일한 case가 나온다 ) 그 나머지씩만 이동한다. 

3) rearrange 함수: 상어의 죽음 처리를 해주고, map에 바뀐 상어의 위치를 갱신하는 함수이다. 

새로운 위치를 저장할 tempMap을 만든 후, sharks 배열을 돌면서 죽지 않은 상어에 대해 그 상어의 위치를 tempMap에 저장한다. 이때 tempMap에 0이 아닌 숫자가 있을 경우 이미 그 칸에 상어가 존재한다는 뜻이므로, 사이즈를 서로 비교해줘서 큰 것을 tempMap에 저장하고 작은 것은 죽음처리 해준다. max 값 갱신과 동일한 원리이다.