[ 알고리즘 ] 코딩 - 백준 17143 - 낚시왕.java

---

문제 링크

www.acmicpc.net/problem/17143

17143번: 낚시왕

---

문제 개요

BOJ 17143 - (자바) 낚시왕 - 시뮬레이션 / 구현

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다.

위치 예시

낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.

1. 낚시왕이 오른쪽으로 한 칸 이동한다.
2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
3. 상어가 이동한다.

상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다. 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한 채로 이동한다.

왼쪽 그림의 상태에서 1초가 지나면 오른쪽 상태가 된다. 상어가 보고 있는 방향이 속도의 방향, 왼쪽 아래에 적힌 정수는 속력이다. 왼쪽 위에 상어를 구분하기 위해 문자를 적었다.

이동 예시

상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.

낚시왕이 상어 낚시를 하는 격자판의 상태가 주어졌을 때, 낚시왕이 잡은 상어 크기의 합을 구해보자.

---

로직

Step 00. 상어의 정보는 위치별로 2차원 리스트 배열(shark_map)로 관리한다. 위치 값에 따라 상어의 정보를 입력받자.

Step 01. 낚시꾼이 현재 x위치의 상어중 땅과 가장 가까운 상어를 잡는다. 2차원 리스트 배열(shark_map)에서 y축만 증가시켜가며 가장 먼저 만난 상어의 사이즈를 더해주고 리스트에서 제거한다.

Step 02. 상어를 이동한다. 이동한 상어의 다음 위치를 리스트(tmp_shark)에 모두 저장해준다. 이동을 하고 난 현재 위치의 상어는 제거해준다. 이때 반복하며 해당 자리에서 지우고 싶다면 Iterator를 이용해서 지우며 진행한다. 처음에 이렇게 했는데 생각해보니 이동하고 나서 해당 자리를 clear 해주면 되는 것이라 코드를 수정했다.

이동할 때 주의할 점은 Speed가 1000으로 지도보다 크고, 지도를 벗어나면 반대로 나오는 것이 아닌 방향만을 바꾸는 것이므로 나머지 연산을 할 때 Speed%((R-1)*2) 혹은 Speed%((C-1)*2)로 해주어야 한다는 것이다.

Step 02 - 1. tmp_shark에 저장된 정보를 이용해서 shark_map을 업데이트 해준다.

Step 03. shark_map에서 겹친 상어가 있다면 가장 큰 상어를 제외하고 모두 제거한다.

Step 04. Step 01 ~ Step 03을 x축 끝까지 반복해서 더해진 크기가 정답!

 

처음에 시간초과를 너무 많이 만났다. 쓸데없는 코드를 줄이고 Speed 연산을 바꾸니 해결됐다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static class Shark {
		int y, x, speed, dir, size;

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

		public Shark(Shark shark) {
			this.y = shark.y;
			this.x = shark.x;
			this.speed = shark.speed;
			this.dir = shark.dir;
			this.size = shark.size;
		}

		@Override
		public String toString() {
			return "size: " + this.size;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stt = new StringTokenizer(br.readLine());
		int R, C, M;
		R = Integer.parseInt(stt.nextToken());
		C = Integer.parseInt(stt.nextToken());
		M = Integer.parseInt(stt.nextToken());

		List<Shark>[][] shark_map = new ArrayList[R + 1][C + 1];

		for (int i = 1; i <= R; i++) {
			for (int j = 1; j <= C; j++) {
				shark_map[i][j] = new ArrayList<Shark>();
			}
		}

		for (int i = 0; i < M; i++) {
			stt = new StringTokenizer(br.readLine());
			int y = Integer.parseInt(stt.nextToken());
			int x = Integer.parseInt(stt.nextToken());
			int s = Integer.parseInt(stt.nextToken());
			int d = Integer.parseInt(stt.nextToken());
			int z = Integer.parseInt(stt.nextToken());
			shark_map[y][x].add(new Shark(y, x, s, d, z));
		} // input end

		int res = process(shark_map, R, C, M);
		System.out.println(res);
	}

	// 전체적인 진행과정
	private static int process(List<Shark>[][] shark_map, int r, int c, int m) {
		int sum = 0;

		// 반복문을 수행하는 것이 낚시꾼의 위치가 옮겨지는 것
		for (int x = 1; x <= c; x++) {
			sum += catch_shark(x, shark_map, r); // 상어를 잡음. 격자판에서 out
			move_sharks(shark_map, r, c, m); // 상어 이동
			eat_shark(shark_map, r, c); // 겹친 상어 제거
		}
		return sum;
	}

	private static void move_sharks(List<Shark>[][] shark_map, int r, int c, int m) {
		int[] dy = { 0, -1, 1, 0, 0 }; // 위 아래 오른쪽 왼쪽
		int[] dx = { 0, 0, 0, 1, -1 };

		List<Shark> tmp_shark = new ArrayList<Shark>();

		for (int i = 1; i <= r; i++) {
			for (int j = 1; j <= c; j++) {
				int length = shark_map[i][j].size();
				if (length <= 0)
					continue;

				for(Shark shark: shark_map[i][j]) {
					int speed = shark.speed;
					int dir = shark.dir;
					
					// 위쪽 혹은 아래쪽
					if(dir == 1 || dir == 2) {
						speed = speed % ((r-1)*2);
					} else { // 왼쪽 혹은 오른쪽
						speed = speed % ((c-1)*2);
					}
					
					int size = shark.size;
					int next_y = i;
					int next_x = j;

					// 상어의 속도만큼 이동
					for (int s = 0; s < speed; s++) {
						next_y = next_y + dy[dir];
						next_x = next_x + dx[dir];
						// 다음 위치가 범위를 벗어남
						if (rangeCheck(next_y, next_x, r, c)) {
							// 상어 위치를 이동 전으로
							next_y = next_y - dy[dir];
							next_x = next_x - dx[dir];
							// 상어 방향 변경
							switch (dir) {
							case 1:
								dir = 2;
								break;
							case 2:
								dir = 1;
								break;
							case 3:
								dir = 4;
								break;
							case 4:
								dir = 3;
								break;
							}
							s--;
							continue;
						}
						// 다음위치로 이동 가능
					} // 이동 end
					tmp_shark.add(new Shark(next_y, next_x, speed, dir, size));
				} // 상어 end
				shark_map[i][j].clear(); // 상어 모두 제거
			} // j end
		} // i end
		for (Shark shark : tmp_shark) { // 상어 재배치
			int y = shark.y;
			int x = shark.x;
			shark_map[y][x].add(shark);
		}
	}

	// 겹친 상어가 있다면 한마리를 제외하고 모두 잡아먹자
	private static void eat_shark(List<Shark>[][] shark_map, int r, int c) {
		for (int i = 1; i <= r; i++) {
			for (int j = 1; j <= c; j++) {
				if (shark_map[i][j].size() < 2)
					continue;
				int max_size = -1;
				Shark max_shark = new Shark(0, 0, 0, 0, 0);
				for (Shark shark : shark_map[i][j]) {
					if (max_size < shark.size) {
						max_size = shark.size;
						max_shark = new Shark(shark);
					}
				}
				shark_map[i][j].clear();
				shark_map[i][j].add(max_shark);
			} // j end
		} // i end
	}

	// 범위 체크
	private static boolean rangeCheck(int next_y, int next_x, int r, int c) {
		return next_y <= 0 || next_y >= r + 1 || next_x <= 0 || next_x >= c + 1;
	}

	// 낚시꾼이 상어를 잡았다!
	private static int catch_shark(int x, List<Shark>[][] shark_map, int r) {
		int sum = 0;
		for (int y = 1; y <= r; y++) {
			for (Shark shark : shark_map[y][x]) {
				sum += shark.size;
				shark_map[y][x].remove(shark);
				return sum;
			}
		}
		return 0;
	}
}