[BOJ 17143] 낚시왕 (Java)

BOJ 17143 낚시왕

난이도 : 골드 1

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

17143번: 낚시왕

 

전략

구현문제이지만 시간초과가 나지 않도록 해야한다.

R, C <= 100 이며 낚시꾼은 C만큼 이동한다.

 

전체 칸에 모두 상어가 있는 최악의 경우 R*C^2 만큼 상어를 움직여야한다.

즉 상어를 움직이는 최대 횟수가 100만이 된다.

 

상어의 속도 s <= 1000 이므로 만약 속도만큼 반복문을 실행하면 상어의 위치 갱신이 10억번 일어난다.

따라서 매초마다 상어의 위치를 갱신시키는 부분에서 시간 초과가 발생하지 않도록 구현해야 한다.

 

    static void moveShark(Shark shark) {

        int step = shark.speed;
        if (shark.dir == 1 || shark.dir == 2) {
            step %= (r - 1) * 2;
        }
        else {
            step %= (c - 1) * 2;
        }

        for (int i = 0; i < step; i++) {
            int ny = shark.y + dy[shark.dir];
            int nx = shark.x + dx[shark.dir];

            if (ny < 1 || ny > r || nx < 1 || nx > c) {
                shark.dir = opposite(shark.dir);
                ny = shark.y + dy[shark.dir];
                nx = shark.x + dx[shark.dir];
            }
            shark.y = ny;
            shark.x = nx;
        }
    }

상어의 위치 갱신을 O(1)만에 할 수 있는 수식을 구하고 싶었지만 실패했다..

대신 방향에 따라 O(R) 또는 O(C) 만에 구할 수 있도록 수정하였다.

 

상어의 방향이 수직 일 때는 (R - 1) * 2만큼 이동하면 제자리로 돌아오며 방향도 같아진다.

상어의 방향이 수평일 때는 (C - 1) * 2만큼 이동하면 제자리로 돌아오며 방향도 같아진다.

 

따라서 두 경우에 맞게 속도에 모듈러 연산을 하여 상어의 속도만큼이 아닌, O(R) 또는 O(C)만큼 위치 갱신을 하도록 하면 시간을 줄일 수 있다.

 

이제 상어로 가득 찬 최악의 경우에서 위치 갱신 실행 횟수는 다음과 같다.

R*C = 상어 수 <= 10000 

C = 라운드 수 (초) <= 100

M = (R - 1) * 2 - 1 또는 (C - 1) * 2 - 1 : 각 상어가 위치에 따라 1초에 위치를 갱신하는 최대 횟수

 

최대 실행 횟수 : R*C^2*M

 

말그래도 최대이며, 중간에 상어가 낚여서 사라지거나, 상어끼리 잡아먹어서 상어의 수가 줄어들 수 있으며

상어의 속도에 따라서 초당 위치 갱신 횟수는 M보다 훨씬 작을 수 있다.

 

시행착오

    static void moveSharks() {

        // 모든 상어 이동
        for (Shark shark : sharks) {
            moveShark(shark);
        }

        Shark[][] newMap = new Shark[r + 1][c + 1];
        Shark small = null;

        for (Shark shark : sharks) {
            // 이미 상어가 있으면 크기가 큰 녀석이 잡아먹는다.
            if (newMap[shark.y][shark.x] != null) {
                Shark big = bigShark(newMap[shark.y][shark.x], shark);

                if (big == shark) small = newMap[shark.y][shark.x];
                else small = shark;

                newMap[shark.y][shark.x] = big;
            } else {
                newMap[shark.y][shark.x] = shark;
            }
        }

        if (small != null)
            sharks.remove(small);

        map = newMap;
    }

상어 리스트를 순회하면서 바로 삭제하면 오류가 발생하므로 small을 저장한 후 순회가 끝난 이후 삭제하도록 하였다.

하지만 1초에 잡아먹히는 상어가 여러 마리인 경우 오직 하나의 상어만 삭제되어 틀리는 문제가 있었다.

 

따라서 삭제할 상어들을 리스트에 저장하도록 수정하였다.

    static void moveSharks() {

        // 모든 상어 이동
        for (Shark shark : sharks) {
            moveShark(shark);
        }

        Shark[][] newMap = new Shark[r + 1][c + 1];
        List<Shark> gc = new ArrayList<>();

        for (Shark shark : sharks) {
            // 이미 상어가 있으면 크기가 큰 녀석이 잡아먹는다.
            if (newMap[shark.y][shark.x] != null) {
                Shark big = bigShark(newMap[shark.y][shark.x], shark);

                if (big == shark) gc.add(newMap[shark.y][shark.x]);
                else gc.add(shark);

                newMap[shark.y][shark.x] = big;
            } else {
                newMap[shark.y][shark.x] = shark;
            }
        }

        for (Shark rm : gc) {
            sharks.remove(rm);
        }

        map = newMap;
    }

 

코드

package BOJ_17143;

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

public class Main {

    static int r, c, m;
    static Shark[][] map;
    static LinkedList<Shark> sharks;

    static final int[] dy = { 0, -1, 1, 0, 0 };
    static final int[] dx = { 0, 0, 0, 1, -1 };

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] inputs = br.readLine().split(" ");
        r = Integer.parseInt(inputs[0]);
        c = Integer.parseInt(inputs[1]);
        m = Integer.parseInt(inputs[2]);

        map = new Shark[r + 1][c + 1];
        sharks = new LinkedList<>();

        while (m-- > 0) {
            inputs = br.readLine().split(" ");
            int y = Integer.parseInt(inputs[0]);
            int x = Integer.parseInt(inputs[1]);

            int speed = Integer.parseInt(inputs[2]);
            int dir = Integer.parseInt(inputs[3]);
            int size = Integer.parseInt(inputs[4]);

            Shark shark = new Shark(speed, dir, size);
            shark.y = y;
            shark.x = x;

            sharks.add(shark);
            map[y][x] = shark;
        }

        System.out.println(solution());

    }

    static int solution() {
        int angler = 1;
        int sum = 0;

        for (; angler <= c; angler++) {
            // 상어 잡기
            for (int i = 1; i <= r; i++) {
                if (map[i][angler] != null) {
                    sum += map[i][angler].size;
                    sharks.remove(map[i][angler]);
                    map[i][angler] = null;

                    break;
                }
            }

            // 상어 이동
            moveSharks();
        }

        return sum;
    }

    static void moveSharks() {

        // 모든 상어 이동
        for (Shark shark : sharks) {
            moveShark(shark);
        }

        Shark[][] newMap = new Shark[r + 1][c + 1];
        List<Shark> gc = new ArrayList<>();

        for (Shark shark : sharks) {
            // 이미 상어가 있으면 크기가 큰 녀석이 잡아먹는다.
            if (newMap[shark.y][shark.x] != null) {
                Shark big = bigShark(newMap[shark.y][shark.x], shark);

                if (big == shark) gc.add(newMap[shark.y][shark.x]);
                else gc.add(shark);

                newMap[shark.y][shark.x] = big;
            } else {
                newMap[shark.y][shark.x] = shark;
            }
        }

        for (Shark rm : gc) {
            sharks.remove(rm);
        }

        map = newMap;
    }

    static void moveShark(Shark shark) {

        int step = shark.speed;
        if (shark.dir == 1 || shark.dir == 2) {
            step %= (r - 1) * 2;
        }
        else {
            step %= (c - 1) * 2;
        }

        for (int i = 0; i < step; i++) {
            int ny = shark.y + dy[shark.dir];
            int nx = shark.x + dx[shark.dir];

            if (ny < 1 || ny > r || nx < 1 || nx > c) {
                shark.dir = opposite(shark.dir);
                ny = shark.y + dy[shark.dir];
                nx = shark.x + dx[shark.dir];
            }
            shark.y = ny;
            shark.x = nx;
        }
    }

    static Shark bigShark(Shark s1, Shark s2) {
        if (s1.size < s2.size) return s2;
        return s1;
    }

    static int opposite(int dir) {
        if (dir == 1) return 2;
        else if (dir == 2) return 1;
        else if (dir == 3) return 4;
        else return 3;
    }


    static class Shark {
        int y;
        int x;
        int dir;

        final int speed;
        final int size;

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

 

깨달은 점

사실 문제만 보고 그래프 탐색도 아니고 엄청 쉽겠다고 생각하면서 시작했다.

하지만 map에서 바로 상어를 움직일 때 아직 움직이지 않은 상어를 잡아먹는다거나 등의 문제들이 있었고, 생각보다 많은 시간을 쓴 문제이다.

앞으로 이런 구현 문제에 대해서 연습을 좀 더 해야할 것 같다고 느꼈다.