BOJ - 17143 낚시왕

17143 낚시왕 : https://www.acmicpc.net/problem/17143

---

Problem

---

Solve

격자판(R,C)이 최대 100이고 상어가 최대로 움직일수 있는 횟수가 최대 1000이다.
낚시왕이 오른쪽으로 이동할수 있는 횟수 최대 100, 상어가 이동하는 경우 1000(100100)이므로 최대 시간복잡도는 1001000100*100 = O(1000000000)가 되므로 기본 반복으로는 해결할수 없다.

여기서 반복을 줄일수 있는 방법은 상어가 이동하는 경우인데, R이 6일때 상어의 이동이 10이라면 동일한 위치에 있게 된다.

상어의 이동이 11이면 이동이 1인것과 동일한 결과를 가지게 된다.

즉, 상어의 이동 횟수를 (격자판의 크기*2)-2의 나머지값으로 치환하게 되면 상어의 이동을 최소한으로 줄일수 있게 된다.

그리고 이동하면서 벽에 닿았을 경우 방향을 바꿔줘야하므로 방향 배열을 {위,왼,아래,오}로 설정하면 (현재방향+2)%4의 계산으로 방향을 반대반향으로 변환해줄수 있다.

---

Solve

public class 낚시왕 {
	static int R;
	static int C;
	static Shark[][] see;
	static int[] dy = {-1, 0, 1, 0};
	static int[] dx = {0, -1, 0, 1};
	static int answer;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		see = new Shark[R][C];
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				see[i][j] = null;
			}
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int y = Integer.parseInt(st.nextToken()) - 1;
			int x = Integer.parseInt(st.nextToken()) - 1;
			int s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken());
			int z = Integer.parseInt(st.nextToken());

			//방향변환을 효율적으로 하기 위해 방향 수정
            //0 : 위, 1: 왼 : 2 : 아래, 3 : 오
			switch (d) {
				case 1:
					d = 0;
					break;
				case 2:
					d = 2;
					break;
				case 3:
					d = 3;
					break;
				case 4:
					d = 1;
					break;
			}
            //상어 이동 최소로 변경
			s = convertSpeed(s, d);
			see[y][x] = new Shark(y, x, s, z, d);
		}

		answer = 0;
        //낚시왕이 오른쪽으로 이동하는 경우
		for (int h = 0; h < R; h++) {
			//낚시
			fishing(h);
			//상어이동
			sharkMove();
		}
		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	//y축이 0에서 부터 가장 가까운 상어부터 잡는다.
	static void fishing(int h) {
		for (int i = 0; i < R; i++) {
			if (see[i][h] != null) {
				answer += see[i][h].size;
				see[i][h] = null;
				break;
			}
		}
	}

	static void sharkMove() {
		Shark[][] copySee = new Shark[R][C];
        //움직인 상어를 한번에 이동시켜야한다.
        //바로 배열에 적용시키면 중복 좌표에 상어가 들어가게되면 잡아먹게 된다.
		List<Shark> moveSharkList = new ArrayList<>();
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (see[i][j] != null) {
					int move = see[i][j].speed;
					int distance = see[i][j].distance;
					int ny = i;
					int nx = j;
					//상하 이동
					if(distance == 0 || distance == 2){
						while(move-- > 0){
							ny += dy[distance];
                            //이동 중 벽에 닿게 되면 방향 변경
							if(ny<0 || ny>=R){
								ny -= dy[distance];
								distance = (distance+2)%4;
								ny += dy[distance];
							}
						}
					}
					//좌우 이동
					else{
						while(move-- > 0){
							nx += dx[distance];
                            //이동 중 벽에 닿게 되면 방향 변경
							if(nx<0 || nx>=C){
								nx -= dx[distance];
								distance = (distance+2)%4;
								nx += dx[distance];
							}
						}
					}

					 moveSharkList.add(new Shark(ny, nx, see[i][j].speed, see[i][j].size, distance));
				}
			}
		}

		//이동한 상어를 복사한 배열에 갱신한다.
        //중복된 위치에 상어가 존재하게 되면 크기가 작은 상어는 잡아 먹힌다.
		for(Shark s : moveSharkList){
			if(copySee[s.y][s.x] != null){
				if(copySee[s.y][s.x].size < s.size){
					copySee[s.y][s.x] = s;
				}
			}else{
				copySee[s.y][s.x] = s;
			}
		}
        //이동한 상어가 갱신된 배열로 변경.
		see = copySee;
	}

	//상어의 이동을 최소로 변경.
	static int convertSpeed(int speed, int distance){
		if(distance == 0 || distance == 2){
			return speed % ((R*2)-2);
		}else{
			return speed % ((C*2)-2);
		}
	}

	static class Shark {
		int y;
		int x;
		int speed;
		int size;
		int distance;

		public Shark(int y, int x, int speed, int size, int distance) {
			this.y = y;
			this.x = x;
			this.speed = speed;
			this.size = size;
			this.distance = distance;
		}
	}

}

---

Result

---

Reference