BOJ(백준 온라인 저지) 17143번 with 자바[JAVA]

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

---

그냥 구현문제이다.

근데 시간복잡도 이슈가 있는...

 

처음 생각

 

그냥 행과 열의 크기가 최대 100이므로 시간복잡도를 생각하지 않고 구현을 해봤다.

상어들이 낚시꾼에 의해 잡히기도 하고 서로 잡아 먹히기도 하니, 삭제가 잦을 거라고 판단 하고,

LinkedList로 상어들을 저장해주었다.

 

그 후 상어들이 이동하고,

LinkedList안에 있는 상어들 중 같은 위치에 있는 상어들을 찾아서(* 물론 선형으로)

잡아 먹는 것 까지 구현을 했다.

 

하지만, LinkedList의 최대길이는 100 x 100 으로 10,000 이고,

List안에 있는 상어들끼리의 관계를 파악하기 위해

두 번 for문을 돌리면 10,000 x 10,000 으로 반드시 시간초과가 발생한다.

 

따라서 2차원 행렬을 만들어서 거기에 상어들을 저장하는 방식을 사용했다.

최대 N^3 까지는 가능하니까(* 100 x 100 x 100 << 100,000,000(1억)) 

 

또한 상어가 움직이는 도중 2차원 행렬을 넘어서는 경우를 구현하기 위해

처음에는 재귀 구조를 생각했다.

 

하지만, 2차원 행렬은 매우 작지만 상어의 속도가 매우 빠른 경우,

재귀 호출이 너무 많이 불려지는 문제가 발생할 수 있을 거라고 판단했다.

 

그래서 나머지와 몫 연산을 통해서 한 번에 움직일 위치를 찾는 방식을 선택했다.

 

코드

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

public class Main {

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

        R = Integer.parseInt(st1.nextToken());
        C = Integer.parseInt(st1.nextToken());
        M = Integer.parseInt(st1.nextToken());

        // 낚시터를 2차원 배열로 생성해서 저장
        Shark[][] sharkMap = new Shark[R][C];
        for(int i=0; i<R; i++){
            Arrays.fill(sharkMap[i], null);
        }

        for(int i=0; i<M; i++){
            StringTokenizer st2 = new StringTokenizer(br.readLine());

            int r, c, sp, d, z;
            r = Integer.parseInt(st2.nextToken()) - 1;
            c = Integer.parseInt(st2.nextToken()) - 1;
            sp = Integer.parseInt(st2.nextToken());
            d = Integer.parseInt(st2.nextToken());
            z = Integer.parseInt(st2.nextToken());

            // 상어 객체를 만들고 낚시터에 저장
            Shark s = new Shark(r, c, sp, d, z);
            sharkMap[r][c] = s;
        }

        // 이미 이동한 상어와 아닌 상어를 구분해준다.
        // 상어가 이동했을때, 이미 그 자리에 있는 경우는 크게 2가지가 있다.
        // 1. 이미 있던 상어가 움직이지 않은 상어였던 경우
        // 2. 이미 있던 상어가 이미 움직인 상어의 경우

        // 1번의 경우, 그냥 미리 있던 상어를 다시 움직여주면 된다.
        // 2번의 경우, 먹을 수 있는지 확인하고 먹힌 상어는 지워준다.

        // 2번의 경우를 구별해 줄 수 있는 index 가 moved 이다.
        boolean[][] moved = new boolean[R][C];
        int ans = 0;
        for(int i=0; i<C; i++){
            // moved 초기화
            for(int j=0; j<R; j++) {
                Arrays.fill(moved[j], false);
            }

            // 낚시를 해서 잡는 물고기의 크기
            int targetSize = 0;
            for(int j=0; j<R; j++){
                if(sharkMap[j][i] != null) {
                    // 낚시꾼과 가까운 물고기를 낚으니 row 를 키우면서 가장 먼저 나오는 물고기를 잡는다.
                    targetSize = sharkMap[j][i].size;
                    // 삭제
                    sharkMap[j][i] = null;
                    break;
                }
            }

            // 만약, 아무것도 없으면 크기는 0으로, 더해도 의미가 없다.
            ans += targetSize;

            // 이동 및 충돌 구현
            // 낚시터를 훑으면서 상어를 이동시켜준다.
            // 총 시간복잡도는 N^2 로 최대 100 x 100 이다.
            for(int j=0; j<R; j++){
                for(int k=0; k<C; k++){
                    // 만약 해당 자리에 있는 상어가 이미 움직인 상어이거나
                    // 상어가 없다면 다음 자리로 넘어간다.
                    if(moved[j][k] || sharkMap[j][k] == null)
                        continue;
                    else{
                        boolean cannotEatalbe = false;
                        Shark s = sharkMap[j][k];
                        // 이동할 상어가 원래 있던 자리는 비워주고,
                        sharkMap[j][k] = null;
                        // 상어는 이동한다.
                        s.move(s.speed);
                        // 상어가 이동할 자리가 빈 자리가 될 때까지 반복해준다.
                        while(sharkMap[s.row][s.col] != null){
                            // 만약 상어가 이동한 자리에 있는 상어가 이미 움직인 상어라면,
                            // 먹거나 먹혀야한다.
                            if(moved[s.row][s.col]){
                                // 미리 있던 상어가 먹히는 경우
                                if(s.eatable(sharkMap[s.row][s.col])){
                                    break;
                                }
                                // 움직인 상어가 먹히는 경우
                                else if(sharkMap[s.row][s.col].eatable(s)){
                                    cannotEatalbe = true;
                                    break;
                                }
                            }
                            // 상어가 이동한 자리에 있는 상어가 움직인 상어가 아닌 경우
                            // 그 상어를 움직여준다.
                            Shark next = sharkMap[s.row][s.col];
                            next.move(next.speed);
                            sharkMap[s.row][s.col] = s;
                            moved[s.row][s.col] = true;
                            s = next;
                        }
                        // 먹었다면 그 자리에 움직인 상어를 저장
                        // 먹혔다면 if 문이 false 이므로, 그냥 지나간다.
                        if(!cannotEatalbe) {
                            sharkMap[s.row][s.col] = s;
                            moved[s.row][s.col] = true;
                        }
                    }
                }
            }
        }

        System.out.println(ans);
    }

    static class Shark {
        int row, col, speed, direct, size;

        Shark(int r, int c, int sp, int d, int s){
            this.row = r;
            this.col = c;
            this.speed = sp;
            this.direct = d;
            this.size = s;
        }

        Shark(){
            this(0,0,0,0,0);
        }

        // 크기가 크다면 먹을 수 있다.
        public boolean eatable(Shark s){
            return s.size < this.size;
        }

        // 움직임에 대한 메소드
        public void move(int n){
            // 위를 향한다면
            if(this.direct == 1){
                // 끝까지 가고 튕겨서 반대로 가는 경우
                if(this.row < n){
                    // 이동거리
                    int hop = n - this.row;
                    // 왕복횟수
                    int a = hop / (R - 1);
                    // 왕복 후 이동 거리
                    int b = hop % (R - 1);

                    // 짝수번 왕복하면 기존 방향에 대해 반대,
                    // 위치는 b 가 된다.
                    if(a % 2 == 0){
                        this.direct = 2;
                        this.row = b;
                    }
                    else{
                        // 홀수번 앙복하면 기존 방향과 일치,
                        // 위치는 R - 1 - b 가 된다.
                        this.row = R - 1 - b;
                    }
                }
                // 끝까지 가지 못해서 튕기지 못하는 경우
                else{
                    this.row -= n;
                }
            }
            // 다른 방향의 경우도 일치한다.
            else if(this.direct == 2){
                if(this.row + n >= R){
                    int hop = n - R + this.row + 1;
                    int a = hop / (R - 1);
                    int b = hop % (R - 1);

                    if(a % 2 == 0){
                        this.direct = 1;
                        this.row = R - 1 - b;
                    }
                    else{
                        this.row = b;
                    }
                }
                else{
                    this.row += n;
                }
            }
            else if(this.direct == 3){
                if(this.col + n >= C){
                    int hop = n - C + this.col + 1;
                    int a = hop / (C - 1);
                    int b = hop % (C - 1);

                    if(a % 2 == 0){
                        this.direct = 4;
                        this.col = C - 1 - b;
                    }
                    else{
                        this.col = b;
                    }
                }
                else{
                    this.col += n;
                }
            }
            else{ // direct == 4
                if(this.col < n){
                    int hop = n - this.col;
                    int a = hop / (C - 1);
                    int b = hop % (C - 1);

                    if(a % 2 == 0){
                        this.direct = 3;
                        this.col = b;
                    }
                    else{
                        this.col = C - 1 - b;
                    }
                }
                else{
                    this.col -= n;
                }
            }
        }
    }
}

 

배움

 

시간복잡도를 고려하는 판단이 좋았음