HwangHub

[Java/시뮬레이션] 백준 17143. 낚시왕 본문

workspace/알고리즘

[Java/시뮬레이션] 백준 17143. 낚시왕

HwangJerry 2024. 4. 2. 20:05
 

17143번: 낚시왕

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

www.acmicpc.net

🤔 Intuition

시뮬레이션 문제인데, 1월부터 4월까지 오랜 기간에 걸쳐 총 3번의 시도 끝에 성공했다.

다시 도전해서 드디어 성공했다...

 

이 문제는 상어가 움직이는 걸 수식으로 구현하는 게 포인트이다. (이걸 그냥 단순 반복으로 한칸한칸 움직이게 구현하면 시간초과 발생, 근데 또 수식으로 구현하려니 머리 아픔)

 

옛날에는 애초에 시뮬레이션 문제를 잘 못풀었고, 2트 째에는 수식 완성을 못했다. 그리고 3트 째에 드디어 풀었다...

🔎 Algorithm & Complexity

* @algorithm simulation
* @time O(R*C*C) : 532 ms
* @memory O(R*C) : 30504 KB

👨🏻‍💻 Logic

  1. 각 column 상 가장 위에 있는 상어를 낚는다.
  2. 상어를 움직인다. 이 때, R-1, C-1 의 두 배를 기준으로 상어는 같은 위치로 돌아오므로 이를 mod 연산을 이용하여 처리해준다. 그 이후 방향이 바뀌는 경우와 아닌 경우를 나눠서 움직이는 위치를 구한다. 
  3. 움직이는 위치에 이미 상어가 있는 경우에는 더 큰 놈만 살려둔다.
public class BOJ_17143_낚시왕 {
    private static int R, C, M, r,c,s,d,z,nr,nc;
    private static int[] dr = {0, -1, 1, 0, 0}; // 상 하 우 좌
    private static int[] dc = {0, 0, 0, 1, -1};
    public static final int UP = 1;
    public static final int DOWN = 2;
    public static final int RIGHT = 3;
    public static final int LEFT = 4;
    private static PriorityQueue<Shark>[] sharks;
    private static Shark[][] temp;
    private static class Shark {
        private int row, col, speed, direction, size;

        private Shark(int r, int c, int s, int d, int z) {
            row = r;
            col = c;
            speed = s;
            direction = d;
            size = z;
        }
    }

    private static class Pair {
        int idx;
        Shark shark;

        private Pair(int idx, Shark shark) {
            this.idx = idx;
            this.shark = shark;
        }
    }
    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());
        sharks = new PriorityQueue[C];

        for (int i = 0; i < C; i++) {
            sharks[i] = new PriorityQueue<>(Comparator.comparingInt(o -> o.row));
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            r = Integer.parseInt(st.nextToken()) - 1;
            c = Integer.parseInt(st.nextToken()) - 1;
            s = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());
            z = Integer.parseInt(st.nextToken());
            sharks[c].add(new Shark(r, c, s, d, z));
        }
        int ans = 0;

        for (int fisherIdx = 0; fisherIdx < C; fisherIdx++) { // 낚시왕이 움직이는 횟수만큼
            // 상어 하나 낚기
            if (!sharks[fisherIdx].isEmpty()) {
//                System.out.println("sharks[fisherIdx].peek().size = " + sharks[fisherIdx].peek().size);
                ans += sharks[fisherIdx].poll().size;
            }

            // 상어 이동하기
            temp = new Shark[R][C];
            List<Pair> delList = new ArrayList<>();
            for (int i = 0; i < C; i++) {
                for (Shark shark : sharks[i]) {
                    r = shark.row;
                    c = shark.col;
                    s = shark.speed;
                    d = shark.direction;
                    z = shark.size;

                    nr = r + dr[d]*s;
                    nc = c + dc[d]*s;

                    if (d == DOWN) {
                        if (nr >= R) {
                            nr = (nr - R) % ((R - 1) * 2);
                            if (nr >= R - 1) {
                                nr = nr - (R - 1) + 1;
                            } else {
                                nr = (R - 1) - (nr + 1);
                                shark.direction = UP;
                            }
                        }
                    } else if (d == UP) {
                        if (nr < 0) {
                            nr = (Math.abs(nr) - 1) % ((R - 1) * 2);
                            if (nr >= R - 1) {
                                nr = (R - 1) - (nr - (R - 1)) - 1;
                            } else {
                                nr = nr + 1;
                                shark.direction = DOWN;
                            }
                        }
                    } else if (d == RIGHT) {
                        if (nc >= C) {
                            nc = (nc - C) % ((C - 1) * 2);
                            if (nc >= C - 1) {
                                nc = nc - (C - 1) + 1;
                            } else {
                                nc = (C - 1) - (nc + 1);
                                shark.direction = LEFT;
                            }
                        }
                    } else if (d == LEFT) {
                        if (nc < 0) {
                            nc = (Math.abs(nc) - 1) % ((C - 1) * 2);
                            if (nc >= C - 1) {
                                nc = (C - 1) - (nc - (C - 1)) - 1;
                            } else {
                                nc = nc + 1;
                                shark.direction = RIGHT;
                            }
                        }
                    }

                    // 위치가 구해졌으니 상어 잡아먹기 진행
                    if (temp[nr][nc] != null) {
                        if (temp[nr][nc].size > shark.size) {
                            continue;
                        }
                    }
                    temp[nr][nc] = shark;
                }
            }

            for (int i = 0; i < C; i++) {
                sharks[i].clear();
            }

            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
//                    System.out.print(temp[i][j] == null ? "0 " : temp[i][j].size + " ");
                    if (temp[i][j] != null) {
                        temp[i][j].row = i;
                        temp[i][j].col = j;
                        sharks[j].add(temp[i][j]);
                    }
                }
//                System.out.println();
            }
//            System.out.println("---------------");

        }
        System.out.println(ans);
    }
}
Comments