[백준] 17143. 낚시왕

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

17143번: 낚시왕

---

이 문제에서는 어떻게 시간초과 나오지 않게 하는지 생각을 해야합니다. 저는 그래서 먼저 상어들의 정보를 가지고 있는 Shark 라는 Class를 만들어서 sharks 라는 배열로 상어들에게 1번부터 번호를 매겼습니다. 그래서 잡힌 상어들을 번호로 쉽게 Null 로 없애고, Null 이면 연산을 수행하지 않게 해서 시간을 줄일 수 있었습니다.

2차원 map 에 각 상어들의 번호를 저장 -> 상어를 잡을 때 catching() -> 잡은 후에 map을 다시 초기화 -> 상어가 이동하고 난 후에 상어들을 map에 다시 표시 하는 방식으로 시간을 줄일 수 있었습니다.

[ 문제 풀이 ]

1. 입력 받은 상어들을 차례대로 1번부터 번호를 붙여 상어가 있는 좌표 map 에 그 번호를 저장합니다.

2. 낚시왕이 한칸 움직일 때 마다 상어를 잡고 catching() -> map 을 초기화 -> 상어를 움직이고 상어들을 map 에 표시하는 moving() 함수를 만들어서 문제를 해결했습니다.

3. catching(i) 는 i 번 째 열에서 가장 가까운 상어의 번호를 찾아서 Null 로 표시하여 다음부터 Null 이면 그 상어는 잡힌 것 이기 때문에 연산을 하지 않았습니다.

4. moving() 함수는 상어들을 움직이는 함수인데, 상어의 속력 s의 최대값이 1000이므로 한칸씩 모두 움직여 보면  시간초과가 나기 때문에 여기서도 연산을 줄여야합니다. 이 부분을 생각해 내지 못해서 다른 블로그를 참고하였는데, 

① 좌우로 움직이는 상어의 경우 speed %= (C*2-2)

② 상하로 움직이는 상어의 경우 speed %= (R*2-2)

위의 두 방법으로 연산을 하면 속도가 아무리 커도 상어가 자기 자리 그대로 위치하고 얼만큼 더 움직여야하는지 speed에 저장되게 됩니다. 노트에 작은 숫자로 간단하게 문제에 주어진 예를 생각해보면 금방 이해 할 수 있는데, 이걸 쉽게 시험장에서 생각하긴 어려울 것 같았습니다.

여기에서 주의할 점은 상어의 시작점이 벽과 붙어있는지 없는지를 판단해야 하는데 왜냐하면 벽에 붙어있는 상어들은 다음 이동이 방향을 바꾸고 한칸 움직이는 것 두 가지 동작을 동시에 하기 때문입니다. 

그리고 나머지 이동은 하나씩 차례대로 움직여서 상어가 최종 위치하는 곳을 map에 표시합니다. 여기에서 상어를 한마리씩 움직이면서 map 에 표시하는데 그 자리에 다른 상어가 있었다면 크기를 비교해서 작은 상어를 null 로 만들어 죽입니다.

---

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	
	static int R, C, M, result;
	static int[][] map, dir = {{0,0},{-1,0},{1,0},{0,1},{0,-1}};	// 북 남 동 서
	static Shark[] sharks;
	static int[] change_dir = {0,2,1,4,3};
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		R = sc.nextInt();
		C = sc.nextInt();
		M = sc.nextInt();
		map = new int[R][C];
		sharks = new Shark[M+1];
	
		for(int i=1; i<=M; i++) {
			int r = sc.nextInt()-1; // 상어 위치 (r, c)
			int c = sc.nextInt()-1;
			int s = sc.nextInt(); // 속력
			int d = sc.nextInt() ; // 이동 방향
			int z = sc.nextInt(); // 크기
			map[r][c] = i;
			sharks[i] = new Shark(r, c, s, d, z);
		}

		// 1. 낚시왕이 한칸씩 움직인다.		
		for(int i=0; i<C; i++) {
			
//			System.out.println("현재 낚시왕이 있는 열의 번호 : " + i);
			// 2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다.
			catching(i);
			
			// 맵을 초기화하고 상어 한마리씩 움직이면서 지도에 표시한다.
			map = new int[R][C];
			
			// 3. 상어가 이동한다.
			moving();
			
			
		}
		
		System.out.println(result);
	}	

	public static void moving() {
		// 1 : 북, 2 : 남, 3 : 동, 4 : 서
		
		for(int i=1; i<=M; i++) {
			if(sharks[i] == null) continue;
			else {
				Shark s = sharks[i];
				int nx = s.r;
				int ny = s.c;
				int direction = s.d;
				int speed = s.s;
				
				if(direction == 1 || direction == 2) speed %= (R*2-2); 
				else if(direction == 3 || direction == 4) speed %= (C*2-2);
					
				for(int j=0; j<speed; j++) {
					nx += dir[direction][0];
					ny += dir[direction][1];
					
					if(nx < 0 || ny < 0 || nx > R-1 || ny > C-1) {
						nx -= dir[direction][0];
						ny -= dir[direction][1];	
						
						direction = change_dir[direction];
						
						nx += dir[direction][0];
						ny += dir[direction][1];
						
						continue;
					}
					
					if( ((direction == 1 || direction == 2) && (nx == 0 || nx == R-1))
							|| ((direction == 3 || direction == 4) && (ny == 0 || ny == C-1))){
						direction = change_dir[direction];
					}
				}
				
				if(map[nx][ny] != 0) {
					if(sharks[map[nx][ny]].z > s.z) { // 겹친 자리에 있는 상어의 크기가 현재 상어의 크기보다 크면
						sharks[i] = null;	// 현재 상어가 잡아먹힘
						continue;
					} else { // 겹친 자리에 있는 상어의 크기가 현재 상어의 크기보다 작으면
						sharks[map[nx][ny]] = null;
					}
				}				
				
				map[nx][ny] = i;
				sharks[i] = new Shark(nx, ny, s.s, direction, s.z);
				
			}
		}
		
		
	}
	
	// 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다.
	public static void catching(int y) {
		
		// 낚시왕이 있는 열에서 가장 가까운 상어를 잡는다.
		for(int i=0; i<R; i++) {
			if(map[i][y] != 0) {
//				System.out.println("현재 잡은 상어의 크기 : " + sharks[map[i][y]].z);
				result += sharks[map[i][y]].z;
				sharks[map[i][y]] = null;
				return;
			}
		}
	}
	
	public static boolean isInside(int x, int y) {
		return x>=0 && x<R && y>=0 && y<C;
	}
}

class Shark {
	int r; // 상어 위치 (r, c)
	int c;
	int s; // 속력
	int d; // 이동 방향
	int z; // 크기
	
	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;
	}
}