백준 17143 낚시왕 - 삼성 SW 역량 테스트 기출

백준 17143 낚시왕 - 삼성 SW 역량 테스트 기출

1. 문제 링크

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

17143번: 낚시왕

 

2. 문제 해결에 대한 아이디어

1. ArrayList<Shark> sharkList에 상어 정보를 담는다.

2. 낚시왕이 한 칸 이동하여 상어 잡음 -> 상어 이동 의 반복이다.

3. 상어를 특정지을 수 있는 것은 크기이다. 따라서 상어를 잡거나 먹을 때 크기를 기준으로 한다.

4. 낚시왕이 잡은 상어의 크기를 기억해 두고, 상어 이동에서 그 상어가 나오면 continue한다.

5. 상어 이동에서 잡아 먹히는 상어의 크기를 ArrayList<Integer> deadList에 저장한다.

6. 상어의 이동이 끝난 뒤 deadList에 있는 상어의 크기를 기준으로 sharkList에서 삭제한다.

7. 상어의 속도를 보정할 필요가 있다.

   . 이 문제에서 행과 열은 최대 크기가 100인 반면, 속도는 최대 1000까지 주어진다.

   . 상어의 위치는 항상 격자이며 경계에 부딪치면 반대 방향으로 바꾸어 움직인다.

   . 이 때문에, 속도에 따라 최종 위치에 도달하기까지 중복된 위치를 몇 번이나 오간다. (시간 초과 발생)

   . 따라서, 상어가 다시 제 자리에 처음에 가진 방향을 가진 상태로 위치하는 비용으로 속도를 보정해준다.

      . 새로운 속도 = 상어의 원래 속도 % (제 자리에 오는 비용)

8. 이 문제의 경우, 제 자리에 오는 비용은 아래와 같다. (나는 직접 종이에 써서 확인했다.)

   . R * 2 - 2 / C * 2 - 2

상어(->)

상어(->)

상어(->)

   . 3 칸의 제 자리 비용 : 4

   . 4 칸의 제 자리 비용 : 6

   . 5 칸의 제 자리 비용 : 8

9. 새로운 속도(이동 횟수)에서 -1을 하며 한 칸씩 이동하는데 방향을 바꾸게 되는 경우 이동 횟수 +1 하여 보정했다.

   . 못 움직였는데 이동 횟수는 감소했으므로

10. 상어의 이동은 새로운 배열(copy)에 기록하고 다시 원래 배열(board)로 옮겨왔다.

 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class Main {
	static class Shark implements Comparable<Shark> {
		int y, x, s, d, z;

		public Shark(int y, int x, int s, int d, int z) {
			super();
			this.y = y;
			this.x = x;
			this.s = s; // 속력
			this.d = d; // 방향
			this.z = z; // 크기
		}

		@Override
		public int compareTo(Shark o) {
			return this.z - o.z;
		}

	}

	static int[][] board;
	static int[][] copy;
	static int R, C, M;
	static int[] dirY = { -1, 1, 0, 0 };
	static int[] dirX = { 0, 0, 1, -1 };
	static int catchSize = -1;
	static ArrayList<Integer> deadList = new ArrayList<>();
	static ArrayList<Shark> sharkList = new ArrayList<>();
	static int fisherJ = -1;
	static int answer = 0;

	public static void main(String[] args) throws IOException {
//		BufferedReader br = new BufferedReader(new FileReader(
//				"C:\\Users\\admin\\git\\java-algorithm\\src\\main\\java\\boj\\삼성기출\\낚시왕_17143\\input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] rcm = br.readLine().split(" ");
		R = Integer.parseInt(rcm[0]);
		C = Integer.parseInt(rcm[1]);
		M = Integer.parseInt(rcm[2]);

		if (M == 0) {
			System.out.println(answer);
			return;
		}

		board = new int[R][C];

		for (int i = 0; i < M; i++) {
			String[] line = br.readLine().split(" ");
			int y = Integer.parseInt(line[0]) - 1; // 위치 보정
			int x = Integer.parseInt(line[1]) - 1; // 위치 보정
			int s = Integer.parseInt(line[2]);
			int d = Integer.parseInt(line[3]) - 1; // 방향 보정
			int z = Integer.parseInt(line[4]);

			if (d < 2) {
				s = s % (R * 2 - 2);
			} else {
				s = s % (C * 2 - 2);
			}

			Shark temp = new Shark(y, x, s, d, z);
			sharkList.add(temp);
			board[y][x] = z;
		}

		while (true) {

			if (!fisherMove())
				break;

			sharkMove();

		}

		System.out.println(answer);
	}

	static boolean fisherMove() {
		++fisherJ;
		if (fisherJ >= C) {
			return false;
		}
		int fisherI = 0;
		while (fisherI != R) {
			if (board[fisherI][fisherJ] != 0) {
				answer += board[fisherI][fisherJ];
				catchSize = board[fisherI][fisherJ];
				board[fisherI][fisherJ] = 0;
				break;
			}
			++fisherI;
		}

		return true;
	}

	static void sharkMove() {
		// 카피에서 해야함
		copy = new int[R][C];
		for (int i = 0; i < sharkList.size(); i++) {
			Shark now = sharkList.get(i);
			if (catchSize == now.z) {
				sharkList.remove(i--);
				continue;
			}
			int y = now.y;
			int x = now.x;
			int s = now.s;
			int d = now.d;

			int yy = y;
			int xx = x;

			while (s-- > 0) {
				yy = y + dirY[d];
				xx = x + dirX[d];

				if (yy >= R || xx >= C || yy < 0 || xx < 0) {
					if (d == 0) {
						d = 1;
						yy = y;
					} else if (d == 1) {
						d = 0;
						yy = y;
					} else if (d == 2) {
						d = 3;
						xx = x;
					} else if (d == 3) {
						d = 2;
						xx = x;
					}

					++s;
				} else {
					y = yy;
					x = xx;
				}
			}
			// 위치와 방향 변경
			now.y = yy;
			now.x = xx;
			now.d = d;
			// 상어 이동
			if (copy[now.y][now.x] == 0) {
				copy[now.y][now.x] = now.z;
			} else {
				if (copy[yy][xx] > now.z) { // now 가 먹힘
					deadList.add(now.z);
				} else {
					deadList.add(copy[yy][xx]);
					copy[now.y][now.x] = now.z;

				}
			}
		}
		// 죽은 상어들 샤크리스트에서 제외
		for (int i = 0; i < deadList.size(); i++) {
			int size = deadList.get(i);
			for (int j = 0; j < sharkList.size(); j++) {
				Shark s = sharkList.get(j);
				if (s.z == size) {
					sharkList.remove(j);
					break;
				}
			}
		}
		// 초기화
		deadList.clear();
		catchSize = -1;
		copyToOrigin();
	}

	static void copyToOrigin() {

		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				board[i][j] = copy[i][j];
			}
		}
	}

}

 

4. 채점 결과

 

5. 느낀 점

1. 처음에 낚시왕이 잡은 상어의 크기, 죽은 상어의 크기를 각각 list에 담고 있었다.

   . 상어 이동에서 매번 잡은 상어들과 죽은 상어들에 이 상어가 있는지 확인하는 바람에 시간초과가 발생했다.

   . 이를 해결하기 위해, 직접 sharkList에서 그 크기를 가진 상어들을 삭제했다.

   . 계속 들고 있어야 하는 데이터인지를 판단하는 능력을 길러야겠다.

2. shark에 구현한 compareTo는 사용하지 않았다.