[JAVA]17143 낚시왕

 📚 문제  

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

17143번: 낚시왕

 

🔍 아이디어  

배열의 사이즈가 작아서 그냥 배열로 저장하여 찾는 방법을 선택하였다.

해당문제에서 시간 초과가 나는 포인트는 상어의 속도라고 판단하여 해당 부분을 따로 처리해 주었다.

상어의 방향이 오른쪽 왼쪽인 경우, 위아래인 경우를 따로 처리하였다.

먼저 오른쪽, 아래쪽인 경우는 velocity만큼 더하고 , 왼쪽 위쪽인 경우에는 velocity만큼 뺀다.

 

만약 위 아래의 경우만 계산한다고 생각하면 

상어가 해당 자리로 동일한 방향으로 돌아오는 경우는 2*(R-1)인 경우 동일하게 돌아오기 때문에 나머지만 이용하기 위해 모듈러 연산을 한다.

만약 숫자가 음수인 경우에는 절댓값을 취해서 계산한다. (대충 원형으로 돌아가는 느낌으로 생각하면 된다)

대충 아래와 같이 각 칸에 방향에 따라 숫자를 가진다고 생각하고 문제를 접근하여 풀었다.

0	아래쪽 0 위쪽 6
1	아래쪽 1 위쪽 5
2	아래쪽 2 위쪽 4
3	3(위쪽, 아래쪽)

마지막으로 현재 위치를 구하는 방법은

R보다 작으면 아래쪽으로 가는 방향 

R보다 크거나 같으면 위쪽으로 올라가는 방향이고, (R)-(현재숫자 - R)으로 계산하면 된다.

해당 문제에서는 칸이 0부터 시작해서 (R-1)- (next - (R -1)) 여서 R-1+R-1-next = 2*R-2-next로 계산하였다.

 

위, 아래쪽을 구하는 풀이와 동일하게 왼쪽오른쪽을 구하는 메서드도 구현하였다.

완료 후에는 해당 위치를 temp 배열에 저장하는 과정을 거친다

이때 만약 이전에 temp의 현재 상어가 저장될 위치에 자신보다 가벼운 친구가 있다면 현재 상어를 넣고 지나간다.

이렇게 한 차례가 끝난 후에는 map=temp를 하여 map을 갱신해 준다.

 

📝 풀이 

package 백준;

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

public class boj_17143_구현_상어 {
    private static class Shark {
        public int velocity;
        public int dir;
        public int weight;

        public Shark(int velocity, int dir, int weight) {
            this.velocity = velocity;
            this.dir = dir;
            this.weight = weight;
        }
    }

    private static int R;
    private static int C;

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

        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

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

        if (m == 0) {
            System.out.println(0);
            return;
        }

        //사람이 이동한다.
        long sum = 0;
        for (int i = 0; i < C; i++) {
            //1 상어 잡기
            for (int j = 0; j < R; j++) {
                if (map[j][i] != null) {
                    sum += map[j][i].weight;
                    map[j][i] = null;
                    break;
                }
            }


            //2 상어들 이동
            Shark[][] temp = new Shark[R][C];
            for (int p = 0; p < R; p++) {
                for (int q = 0; q < C; q++) {
                    if (map[p][q] != null) {
                        Shark shark = map[p][q];
                        int[] mv = null;
                        switch (map[p][q].dir) {
                            case 1:
                            case 2://위쪽 아래
                                mv = findNextRowLocal(p, q, shark);
                                break;
                            case 3:
                            case 4://오 왼
                                mv = findNextColLocal(p, q, shark);
                                break;
                        }

                        if (temp[mv[0]][mv[1]] == null) {
                            temp[mv[0]][mv[1]] = shark;
                        } else if (temp[mv[0]][mv[1]].weight < shark.weight) { //더 무거운 상어로 바꾼다
                            temp[mv[0]][mv[1]] = shark;
                        }
                    }
                }
            }
            map = temp;
        }

        System.out.println(sum);

    }

    private static int[] findNextRowLocal(int i, int j, Shark shark) {//위 아래
        int next = (shark.dir == 1) ? i - shark.velocity : i + shark.velocity; // 1인 경우 위쪽, 2인 경우 아래쪽
        if (next <= 0 || R - 1 <= next) {
            next = Math.abs(next);
            next %= (2 * R - 2); //한바퀴를 도는 경우 현재 상태와 일치하기떄문에
            if (next < R) {
                shark.dir = 2; //아래쪽
            } else {
                next = (2 * R - next - 2);
                shark.dir = 1; //위쪽(한 바퀴를 넘어가서)
            }

        }

        return new int[]{next, j};
    }


    private static int[] findNextColLocal(int i, int j, Shark shark) { //오 왼
        int next = (shark.dir == 4) ? j - shark.velocity : j + shark.velocity; //3인경우 오른쪽, 4인경우 외쪽
        if (next <= 0 || C - 1 <= next) {
            next = Math.abs(next);
            next %= (2 * C - 2); //한바퀴를 도는 경우 현재 상태와 일치하기떄문에
            if (next < C) {
                shark.dir = 3; //오른쪽
            } else {
                next = (2 * C - next - 2);
                shark.dir = 4; //왼쪽(한바퀴를 넘어감)
            }
        }

        return new int[]{i, next};
    }
}

 

 

아래는 주석을 풀면 상어의 상태를 직관적으로 확인할 수 있어 추가하였다.

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

public class Main {
    private static class Shark {
        public int velocity;
        public int dir;
        public int weight;

        public Shark(int velocity, int dir, int weight) {
            this.velocity = velocity;
            this.dir = dir;
            this.weight = weight;
        }

//        @Override
//        public String toString() {
//            return "Shark{" +
//                    "velocity=" + velocity +
//                    ", dir=" + dir +
//                    ", weight=" + weight +
//                    '}';
//        }
    }

    private static int R, C, M;
    private static Shark[][] map;
    private static Shark[][] temp;

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

        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

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

//        System.out.println("START");
//        for (int p = 0; p < R; p++) {
//            for (int q = 0; q < C; q++) {
//                if (map[p][q] == null) {
//                    System.out.printf("%35s", "No |");
//                } else System.out.printf("%s|", map[p][q]);
//            }
//            System.out.println();
//        }
//        System.out.println("------------------------------------------------------------------------------------------------");

        if (M == 0) {
            System.out.println(0);
            return;
        }

        //사람이 이동한다.
        long sum = 0;
        for (int i = 0; i < C; i++) {
            //1 상어 잡기
            for (int j = 0; j < R; j++) {
                if (map[j][i] != null) {
                    sum += map[j][i].weight;
                    map[j][i] = null;
                    break;
                }
            }


            temp = new Shark[R][C];
            //2 상어들 이동
            Shark[][] temp = new Shark[R][C];
            for (int p = 0; p < R; p++) {
                for (int q = 0; q < C; q++) {
                    if (map[p][q] != null) {
                        Shark shark = map[p][q];
                        int[] mv = null;
                        switch (map[p][q].dir) {
                            case 1:
                            case 2://위쪽 아래:
                                mv = findNextRowLocal(p, q, shark);
                                break;
                            case 3:
                            case 4://왼 dh
                                mv = findNextColLocal(p, q, shark);
                                break;
                        }

                        if (temp[mv[0]][mv[1]] == null) {
                            temp[mv[0]][mv[1]] = shark;
                        } else if (temp[mv[0]][mv[1]].weight < shark.weight) { //더 무거운 상어로 바꾼다
                            temp[mv[0]][mv[1]] = shark;
                        }
                    }
                }
            }
//            System.out.println("col : " + i);
//            for (int p = 0; p < R; p++) {
//                for (int q = 0; q < C; q++) {
//                    if (temp[p][q] == null) {
//                        System.out.printf("%35s", "No |");
//                    } else System.out.printf("%s|", temp[p][q]);
//                }
//                System.out.println();
//            }
//            System.out.println(sum);
//            System.out.println("------------------------------------------------------------------------------------------------");


            map = temp;
        }

        System.out.println(sum);

    }

    private static int[] findNextRowLocal(int i, int j, Shark shark) {//위 아래
        int next = (shark.dir == 1) ? i - shark.velocity : i + shark.velocity; // 1인 경우 위쪽, 2인 경우 아래쪽
        if (next <= 0 || R - 1 <= next) {
            next = Math.abs(next);
            next %= (2 * R - 2); //한바퀴를 도는 경우 현재 상태와 일치하기떄문에
            if (next < R) {
                shark.dir = 2; //아래쪽
            } else {
                next = (2 * R - next - 2);
                shark.dir = 1; //위쪽(한 바퀴를 넘어가서)
            }

        }

        return new int[]{next, j};
    }


    private static int[] findNextColLocal(int i, int j, Shark shark) { //오 왼
        int next = (shark.dir == 4) ? j - shark.velocity : j + shark.velocity; //3인경우 오른쪽, 4인경우 외쪽
        if (next <= 0 || C - 1 <= next) {
            next = Math.abs(next);
            next %= (2 * C - 2); //한바퀴를 도는 경우 현재 상태와 일치하기떄문에
            if (next < C) {
                shark.dir = 3; //오른쪽
            } else {
                next = (2 * C - next - 2);
                shark.dir = 4; //왼쪽(한바퀴를 넘어감)
            }
        }

        return new int[]{i, next};
    }
}