백준 17143 : 낚시왕

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

17143번: 낚시왕

[ 문제풀이 ]

이번에도 역시 주어진 조건대로 시뮬레이션하는 문제이다. 문제를 해결하는 다양한 방법이 존재하겠지만 나는 우선순위 큐를 활용하여 각 좌표의 상어들을 관리하는 식으로 해결하였다.

​주의해야 할 점은 상어를 이동시킬 때 상어의 속도만큼 이동하는 방식으로 처리한다면 시간 초과가 발생할 것이다.

상어는 최대 1만 마리이며 상어의 속력은 최대 1000이기 때문에 단순히 이동시킨다면 최악의 경우 한 번의 이동에 약 천만 번의 연산이 필요하다. 이는 상당히 비효율적이다.

이 부분을 어떻게 줄일 수 있을까? 잘 생각해 보면 우리는 상어의 위치를 모든 경우를 안 돌려봐도 알 수 있다. 한 번 그림으로 이해해 보자.

​현재 c가 7이며 1000의 속도를 가진 상어가 3의 위치에 있다고 하자.

자세히 보면 상어를 12번 이동시키면 원래의 위치로 돌아온다는 것을 알 수 있다. 이를 통해 우리는 상어의 속도를 12로 mod 연산 후 1~11의 이동만 처리해 준다면 훨씬 효율적으로 이동시킬 수 있다.

상어의 방향이 상하 : 상어의 속도 %= (행의 크기 - 1) * 2
상어의 방향이 좌우 : 상어의 속도 %= (열의 크기 - 1) * 2

또한, 우선순위 큐를 사용해서 해결한다면 조심해야 할 점이 한 가지 있다. 우선순위 큐의 우선순위를 상어의 크기가 큰 순으로만 한다면 상어를 제거하는 과정에서 다음과 같은 모순이 생긴다.

이를 해결하기 위해 상어의 시간을 관리하는 time 변수를 사용해서 우선순위 큐의 우선순위를 첫째로 시간이 큰 순서, 두 번째로 크기가 큰 순서로 관리하도록 하였다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int r, c, m, score;
	static Shark[] shark;
	static Queue<Shark>[][] map;

	static int[][] dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

	static class Shark implements Comparable<Shark>{
		int idx, time, r, c, s, d, z;

		public Shark(int idx, int time, int r, int c, int s, int d, int z) {
			this.idx = idx;
			this.time = time;
			this.r = r;
			this.c = c;
			this.s = s;
			this.d = d;
			this.z = z;
		}

		//우선순위 큐를 활용하여 가장 크기가 큰 상어를 관리
		//다만,상어를 이동할때 이동할 위치에 상어가 존재할 경우 단순히 크기로만 관리한다면 모순이 생김 
		//ex)상어A를 상어B의 위치로 이동 후 상어B를 이동시킬 경우 
        //만약, 상어A가 상어B보다 크기가 크다면 B위치의 우선순위 큐는 상어A를 뽑아냄
		//이를 해결하기 위해 time이라는 변수를 통해 상어의 시간을 관리해줌
		public int compareTo(Shark o) {
			if (this.time == o.time) return o.z - this.z;
			return this.time - o.time;
		}
	}

	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());
		m = Integer.parseInt(st.nextToken());

		map = new PriorityQueue[r + 1][c + 1];
		for (int i = 0; i <= r; ++i) {
			for (int j = 0; j <= c; ++j) {
				map[i][j] = new PriorityQueue<>();
			}
		}

		shark = new Shark[m + 1];
		for (int i = 1; i <= m; ++i) {
			st = new StringTokenizer(br.readLine());
			int rr = Integer.parseInt(st.nextToken());
			int cc = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			int d = Integer.parseInt(st.nextToken()) - 1;
			int z = Integer.parseInt(st.nextToken());

			//상어의 이동횟수를 단순히 이동시킨다면 시간초과가 발생함
			//이를 해결하기 위해 자신의 위치로 가는 이동횟수만큼 mod연산 처리
			if (d <= 1) s %= 2 * (r - 1);
			else s %= 2 * (c - 1);
			
			shark[i] = new Shark(i, 0, rr, cc, s, d, z);
			map[rr][cc].offer(shark[i]);
		}

		for (int start = 1; start <= c; ++start) {
			//상어를 낚시
			pickShark(start);
			//살아있는 상어를 이동
			moveShark();
			//한 곳에 2마리 이상이 존재한다면 제거
			removeShark();
		}

		bw.write(score + "\n");
		bw.flush();bw.close();br.close();
	}

	public static void pickShark(int start) {
		//start열의 1행부터 내려가면서 상어가 있다면 없애줌
		for (int i = 1; i <= r; ++i) {
			if (!map[i][start].isEmpty()) {
				Shark s = map[i][start].poll();
				score += s.z;
				shark[s.idx] = null;
				return;
			}
		}
	}

	public static void moveShark() {
		for (int i = 1; i <= m; ++i) {
			if (shark[i] == null) continue;

			int rr = shark[i].r;
			int cc = shark[i].c;
			int nr = rr + dir[shark[i].d][0] * shark[i].s;
			int nc = cc + dir[shark[i].d][1] * shark[i].s;

			//상어를 이동시킴
			if (shark[i].d <= 1) {
				if (nr > r) {
					int diff = nr - r;
					if (diff <= r - 1) {
						nr = r - diff;
						shark[i].d = 0;
					} else {
						nr = diff - r + 2;
					}
				} else if (nr < 1) {
					int diff = -nr;
					if (diff <= r - 2) {
						nr = diff + 2;
						shark[i].d = 1;
					} else {
						nr = (r - 1) * 2 - diff;
					}
				}
			} else {
				if (nc > c) {
					int diff = nc - c;
					if (diff <= c - 1) {
						nc = c - diff;
						shark[i].d = 3;
					} else {
						nc = diff - c + 2;
					}
				} else if (nc < 1) {
					int diff = -nc;
					if (diff <= c - 2) {
						nc = diff + 2;
						shark[i].d = 2;
					} else {
						nc = (c - 1) * 2 - diff;
					}
				}
			}

			map[shark[i].r][shark[i].c].poll();

			shark[i].r = nr; shark[i].c = nc;
			shark[i].time++;

			map[nr][nc].offer(shark[i]);			
		}
	}

	public static void removeShark() {
		for (int i = 1; i <= r; ++i) {
			for (int j = 1; j <= c; ++j) {
				if (map[i][j].isEmpty()) continue;
                
                //크기가 가장 큰 상어만 살아있음
				Shark live = map[i][j].poll();

				//남은 상어들을 제거해줌
				while (!map[i][j].isEmpty()) {
					Shark die = map[i][j].poll();
					shark[die.idx] = null;
				}

				map[i][j].offer(live);
			}
		}
	}
}