[백준] 17143번: 낚시왕 - java

나의 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static class Shark {
		int speed;
		int dir;
		int size;

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

	static int R, C, M, shark_sum;
	static int[][] map;
	static int[] dx = { 0, -1, 1, 0, 0 };
	static int[] dy = { 0, 0, 0, 1, -1 };
	static HashMap<Integer, Shark> sharks = new HashMap<>();

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

		map = new int[R][C];
		int r, c, s, d, z;
		for (int i = 1; i <= M; i++) {
			st = new StringTokenizer(br.readLine());
			r = Integer.parseInt(st.nextToken());
			c = Integer.parseInt(st.nextToken());
			s = Integer.parseInt(st.nextToken());
			d = Integer.parseInt(st.nextToken());
			z = Integer.parseInt(st.nextToken());
			map[r - 1][c - 1] = i; // i번 상어
			sharks.put(i, new Shark(s, d, z)); // i번 상어 저장
		}
		
		
		
		run();
		System.out.println(shark_sum);
	}

	static void run() {
		
		int col = 0;
		while (col < C) {

			// 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다.
			for (int i = 0; i < R; i++) {
				if (map[i][col] > 0) {
					shark_sum += sharks.get(map[i][col]).size;
					map[i][col] = 0; // 상어 잡기
					break;
				}
			}

			// 상어가 이동한다.
			move();
			
			// 낚시왕이 오른쪽으로 한 칸 이동한다.
			col++;
		}
	}

	static void move() {
		int[][] tmp = new int[R][C];

		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (map[i][j] > 0) { // 상어라면 tmp에 움직임 표시하기
					Shark shark = sharks.get(map[i][j]);
					int speed = shark.speed;
					int dir = shark.dir;
					if (dir <= 2)
						speed %= (R * 2 - 2);
					else
						speed %= (C * 2 - 2);

					int nx = i;
					int ny = j;
					for (int s = 1; s <= speed; s++) {
						nx += dx[dir];
						ny += dy[dir];
						if (nx < 0 || nx >= R || ny < 0 || ny >= C) { // 범위 벗어나면 방향 전환
							if (dir == 1)
								dir = 2;
							else if (dir == 2)
								dir = 1;
							else if (dir == 3)
								dir = 4;
							else if (dir == 4)
								dir = 3;

							nx += dx[dir] * 2;
							ny += dy[dir] * 2;
						}
					}
					shark.dir = dir;
					sharks.put(map[i][j], shark);

					if (tmp[nx][ny] > 0) { // 기존에 상어가 들어있다면
						if (sharks.get(tmp[nx][ny]).size < shark.size) { // 기존 상어보다 더 크다면
							tmp[nx][ny] = map[i][j]; // 상어 번호 표시
						}
					} else
						tmp[nx][ny] = map[i][j];
				}
			}
		}
		for(int i=0; i<R; i++) {
			for(int j=0; j<C; j++) {
				map[i][j] = tmp[i][j]; // 원본으로 이동
			}
		}
	}
}

key : 상어의 번호 / value : [상어의 속력, 이동방향, 크기] 를 저장하는 sharks HashMap 을 두어, O(1) 로 상어의 정보를 확인할 수 있도록 한다.

상어 정보를 쉽게 저장하기 위해 Shark class 를 만들었다.

map[i][j] 에는 상어의 번호만을 기록한다.

 

 

 

1. 낚시왕이 있는 현재 열에서 가장 행번호가 작은 상어를 잡는다.

 

 

2. 상어 이동

• 상어들이 움직인 것을 새로운 배열 tmp에 기록하고, 모두 이동한 후 tmp를 원래의 배열 map으로 옮긴다.
  • 상어들은 동시에 움직이기 때문에, 비어있는 tmp 배열을 생성해야 하는 것!
• 속력은 ~1000으로, 1000번을 다 움직여보는 것은 시간이 매우 많이 걸릴 것이다.
  • 따라서 방향이 아래 위라면 (R*2)-2 , 왼쪽오른쪽이라면 (C*2)-2 으로 나눈 나머지 값 만큼만 탐색하도록 한다.
  • 이는 상어가 다시 원래 있던 자리에 같은 방향으로 오는 이동횟수이다.
  • 즉, (R*2)-2 or (C*2)-2 을 주기로 이동이 반복됨을 뜻한다.

• 상어가 움직일 때 만약 0~R-1/C-1 범위를 벗어난다면, 방향을 변경하고, 반대방향으로 다시 이동한다.

• 상어의 방향이 바꼈다면, sharks 를 갱신해줘야 한다.

• 상어 이동이 끝난후, tmp 에 기록해야 한다. 이때 tmp에 이미 다른 상어가 들어있다면 크기를 비교하여, 더 큰 상어만을 남겨 둔다.

• 1초가 지난 후, 상어들이 모두 이동완료했다면 기존 배열로 이동한 상어들의 위치를 복사한다.