[BOJ] 17143. 낚시왕 - Simulation

[BOJ] 17143. 낚시왕 - Simulation

제출일 : 2019-10-18

문제 풀이 시간 : 4H

난이도 : ★★★

Problem

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

Input

첫째 줄에 격자판의 크기 R, C와 상어의 수 M이 주어진다. (2 ≤ R, C ≤ 100, 0 ≤ M ≤ R×C)

둘째 줄부터 M개의 줄에 상어의 정보가 주어진다. 상어의 정보는 다섯 정수 r, c, s, d, z (1 ≤ r ≤ R, 1 ≤ c ≤ C, 0 ≤ s ≤ 1000, 1 ≤ d ≤ 4, 1 ≤ z ≤ 10000) 로 이루어져 있다. (r, c)는 상어의 위치, s는 속력, d는 이동 방향, z는 크기이다. d가 1인 경우는 위, 2인 경우는 아래, 3인 경우는 오른쪽, 4인 경우는 왼쪽을 의미한다.

두 상어가 같은 크기를 갖는 경우는 없고, 하나의 칸에 둘 이상의 상어가 있는 경우는 없다.

Output

낚시왕이 잡은 상어 크기의 합을 출력한다.

Example

input

4 6 8
4 1 3 3 8
1 3 5 2 9
2 4 8 4 1
4 5 0 1 4
3 3 1 2 7
1 5 8 4 3
3 6 2 1 2
2 2 2 3 5

output

22

Solution & Inpression

시뮬레이션 문제

요즘 계속 DFS와 BFS를 응용한 문제들만 풀어서 시뮬레이션 문제가 다시 어렵게 느껴졌다.

최악의 경우 맵의 크기는 100x100이고 상어는 최대 100x100마리이고 모든 상어의 속력이 1000이라면

10,000,000,000번의 연산을 수행해야 한다고 생각을 했기 때문에 무식하게 상어를 움직이면 안된다고 생각을하여 위치와 속도와 방향을 계산하여 상어를 한번에 옮기고 싶어 오랫동안 고민했지만, 식이 세워지지 않았다.

나중에 다시 식을 세워 풀어봐야 겠다.

Code

언어 : JAVA

메모리 : 61,940 kb

실행시간 : 1,604 ms

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    static int R, C, M;
    static int[][] map;
    static ArrayList<Shark> list;

    static class Shark {
        int r, c, speed, direction, size;

        public Shark(int r, int c, int speed, int direction, int size) {
            this.r = r;
            this.c = c;
            this.speed = speed;
            this.direction = direction;
            this.size = size;
        }

        void move() {
            if (direction == 1) { // 위쪽 방향
                int dir = -1; // 움직여야 하는 방향
                for (int i = 0; i < speed; i++) {
                    r += dir;
                    if (r == 0 || r == R + 1) {
                        dir *= -1;
                        r += dir*2;
                    }
                }
                if (dir == 1) // 바뀐 방향이 아래쪽이면
                    direction = 2;
            } else if (direction == 2) {
                int dir = 1; // 움직여야 하는 방향
                for (int i = 0; i < speed; i++) {
                    r += dir;
                    if (r == 0 || r == R + 1) {
                        dir *= -1;
                        r += dir*2;
                    }
                }
                if (dir == -1) // 바뀐 방향이 위쪽이면
                    direction = 1;
            } else if (direction == 3) { // 오른쪽
                int dir = 1; // 움직여야 하는 방향
                for (int i = 0; i < speed; i++) {
                    c += dir;
                    if (c == 0 || c == C + 1) {
                        dir *= -1;
                        c += dir*2;
                    }
                }
                if (dir == -1) // 바뀐 방향이 왼쪽이면
                    direction = 4;
            } else { // 왼쪽
                int dir = -1; // 움직여야 하는 방향
                for (int i = 0; i < speed; i++) {
                    c += dir;
                    if (c == 0 || c == C + 1) {
                        dir *= -1;
                        c += dir*2;
                    }
                }
                if (dir == 1) // 바뀐 방향이 오른쪽이면
                    direction = 3;
            }

        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();

        M = sc.nextInt();
        list = new ArrayList<>();
        map = new int[R][C];
        for (int k = 0; k < M; k++) {
            int i = sc.nextInt();
            int j = sc.nextInt();
            list.add(new Shark(i, j, sc.nextInt(), sc.nextInt(), sc.nextInt()));
        }

        int ans = 0;
        for (int king = 1; king <= C; king++) {
            sort();
            for (int j = 0; j < list.size(); j++) {
                if (list.get(j).c == king) {
                    ans += list.get(j).size;
                    list.remove(j); // 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다
                    break;
                }
            }
            for (int j = 0; j < list.size(); j++) {
                list.get(j).move();
            }
        }
        System.out.println(ans);
    }

    static void sort() {
        Collections.sort(list, new Comparator<Shark>() {
            public int compare(Shark o1, Shark o2) {
                if (o1.r - o2.r != 0) {
                    return o1.r - o2.r;
                } else {
                    if (o1.c - o2.c != 0)
                        return o1.c - o2.c;
                    else {
                        return o2.size - o1.size;
                    }
                }
            }
        });

        for (int i = 0; i < list.size() - 1; i++) {
            Shark s1 = list.get(i);
            Shark s2 = list.get(i + 1);
            if (s1.r == s2.r && s1.c == s2.c) {// 위치가 같으면
                //System.out.println("EAT");
                list.remove(i + 1);
                i--;
            }
        }
    }
}