낚시왕

문제

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

낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하면 이동을 멈춘다.

1. 낚시왕이 오른쪽으로 한 칸 이동한다.
2. 낚시왕이 있는 열에 있는 상어 중에서 땅과 제일 가까운 상어를 잡는다. 상어를 잡으면 격자판에서 잡은 상어가 사라진다.
3. 상어가 이동한다.

상어는 입력으로 주어진 속도로 이동하고, 속도의 단위는 칸/초이다. 상어가 이동하려고 하는 칸이 격자판의 경계를 넘는 경우에는 방향을 반대로 바꿔서 속력을 유지한채로 이동한다.

왼쪽 그림의 상태에서 1초가 지나면 오른쪽 상태가 된다. 상어가 보고 있는 방향이 속도의 방향, 왼쪽 아래에 적힌 정수는 속력이다. 왼쪽 위에 상어를 구분하기 위해 문자를 적었다.

상어가 이동을 마친 후에 한 칸에 상어가 두 마리 이상 있을 수 있다. 이때는 크기가 가장 큰 상어가 나머지 상어를 모두 잡아먹는다.

낚시왕이 상어 낚시를 하는 격자판의 상태가 주어졌을 때, 낚시왕이 잡은 상어 크기의 합을 구해보자.

입력
첫째 줄에 격자판의 크기 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인 경우는 왼쪽을 의미한다.

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

출력

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

예제 입력 1

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

예제 출력 1

22

각 칸의 왼쪽 아래에 적힌 수는 속력, 오른쪽 아래는 크기, 왼쪽 위는 상어를 구분하기 위한 문자이다. 오른쪽 위에 ❤️는 낚시왕이 잡은 물고기 표시이다.

초기상태

1초

2초 (E번 상어는 B번에게 먹혔다)

3초

4초

5초

6초

예제 입력 2

100 100 0

예제 출력 2

0

예제 입력 3

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

예제 출력 3

22

예제 입력 4

2 2 4
1 1 1 1 1
2 2 2 2 2
1 2 1 2 3
2 1 2 1 4

예제 출력 4

4

문제 풀이

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

public class BJ17143 {
    static int[][] moves={{-1,0},{1,0},{0,1},{0,-1}};    //이동하는 방향
    static Shark[][] map;     // 상어가 있는 위치 표시
    static int result;
    static int R,C;

    public static class Shark{
        int s,d,z;

        public Shark(int s,int d,int z){
            this.s=s;
            this.d=d;
            this.z=z;
        }
    }

    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());
        int 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);
        }


        // 낚시꾼이 이동하는 시간, 위치
        for(int time=0;time<C;time++){
            // 상어 잡기
            for(int i=0;i<R;i++){
                if(map[i][time]!=null){
                    result+=map[i][time].z;
                    map[i][time]=null;
                    break;
                }
            }

            // 상어 이동
            sharkMove();
        }

        System.out.println(result);
    }

    private static void sharkMove() {
        Shark[][] copy=new Shark[R][C];

        //각 상어들 이동시키기
        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                Shark shark=map[i][j];
                if(shark!=null){
                    int x=i+moves[shark.d-1][0]*shark.s;
                    int y=j+moves[shark.d-1][1]*shark.s;

                    int tmpD=shark.d;
                    //거리를 초과한 경우
                    while (x<0 ||x>=R || y<0 || y>=C) {
                        if(x<0){
                            //위 -> 아래로 변경
                            tmpD=2;
                            x=Math.abs(x);
                        }else if(x>=R){
                            //아래 -> 위로 변경
                            tmpD=1;
                            x=2*R-x-2;
                        }else if(y<0){
                            //왼 -> 오로 변경
                            tmpD=3;
                            y= Math.abs(y);
                        }else if(y>=C){
                            //오 -> 왼으로 변경
                            tmpD=4;
                            y=2*C-y-2;
                        }
                    }

                    //이동할 자리에 이미 상어가 있다면 크기가 큰 상어만 넣어주기
                    if(copy[x][y]!=null){
                        if(copy[x][y].z<shark.z){
                            copy[x][y]=new Shark(shark.s,tmpD,shark.z);
                        }
                    }else{
                        copy[x][y]=new Shark(shark.s,tmpD,shark.z);
                    }

                }
            }
        }

        for(int i=0;i<R;i++){
            for(int j=0;j<C;j++){
                //copy map 에 옮겨주기
                map[i][j]=copy[i][j];
            }
        }

    }
}

낚시왕은 옆으로 한칸씩 이동하게 되고 상어는 각자의 방향과 속력대로 움직이게된다.

고려해야할 점은 다음과 같다.

• 낚시왕이 이동함에 따라 해당 열에 있는 상어를 잡게된다.
  • 해당 열 중에 제일 높이 있는 상어 제거
• 상어의 이동
  • 각 상어의 방향과 속력에 따라 이동시켜주기
  • 상어가 경계를 넘어서게 되면 반대 방향으로 돌아오기
  • 도착하는 위치에 다른 상어가 있다면 크기를 비교하여 큰 상어만 남기기

상어의 이동에서 고려해야할 점이 많으니 하나씩 생각하여 코드를 구현해주는 것이 중요하다.

상어의 정보 담기

public static class Shark{
    int s,d,z;

    public Shark(int s,int d,int z){
        this.s=s;	//속력
        this.d=d;	//방향
        this.z=z;	//크기
    }
}

...

//main
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);
}

상어의 정보를 하나씩 받고 격자판의 상어 위치에 정보를 담아준다.

그를 위해 Shark라는 class를 생성하여 상어의 정보를 적는다.

낚시왕의 이동

// 낚시꾼이 이동하는 시간, 위치
for(int time=0;time<C;time++){
    // 상어 잡기
    for(int i=0;i<R;i++){
        if(map[i][time]!=null){
            result+=map[i][time].z;
            map[i][time]=null;
            break;
        }
    }
    
    // 상어 이동
    sharkMove();
}

낚시왕이 이동하는 방법은 1초에 한칸씩 오른쪽으로 가는 것이다. 즉, 격자판 기준으로 보면 1열씩 증가하게 되는 것이므로 for문을 이용하여 격자판의 열 크기만큼 하나씩 이동시켜 상어를 잡고, 상어를 이동시켜주면 된다.

한 칸 이동하면 해당 열을 탐색하여 제일 처음 발견한 상어의 크기를 result 값에 추가해주고 해당 위치에 있는 상어는 없애준다. 즉, null로 만들어준다.

상어를 잡은 뒤에는 낚시왕이 해야할 일이 끝났으므로 상어가 이동한다.

상어의 이동

private static void sharkMove() {
    Shark[][] copy=new Shark[R][C];

    //각 상어들 이동시키기
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            Shark shark=map[i][j];
            if(shark!=null){
                int x=i+moves[shark.d-1][0]*shark.s;
                int y=j+moves[shark.d-1][1]*shark.s;

                int tmpD=shark.d;
                //거리를 초과한 경우
                while (x<0 ||x>=R || y<0 || y>=C) {
                    if(x<0){
                        //위 -> 아래로 변경
                        tmpD=2;
                        x=Math.abs(x);
                    }else if(x>=R){
                        //아래 -> 위로 변경
                        tmpD=1;
                        x=2*R-x-2;
                    }else if(y<0){
                        //왼 -> 오로 변경
                        tmpD=3;
                        y= Math.abs(y);
                    }else if(y>=C){
                        //오 -> 왼으로 변경
                        tmpD=4;
                        y=2*C-y-2;
                    }
                }

                //이동할 자리에 이미 상어가 있다면 크기가 큰 상어만 넣어주기
                if(copy[x][y]!=null){
                    if(copy[x][y].z<shark.z){
                        copy[x][y]=new Shark(shark.s,tmpD,shark.z);
                    }
                }else{
                    copy[x][y]=new Shark(shark.s,tmpD,shark.z);
                }

            }
        }
    }

    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            //copy map 에 옮겨주기
            map[i][j]=copy[i][j];
        }
    }

}

격자판을 탐색하여 상어가 있다면 해당 상어의 정보를 받아오고 그 상어가 바라보고 있는 방향으로 속력만큼 이동한다.

즉, 상하좌우로 만들어둔 moves 배열값에서 현재위치 + 해당 방향의 값 x 상어 속력 을 해주면 상어가 이동하게 되는 것이다.

이때, 주의해야할 점은 현재위치 + 해당 방향의 값 x 상어 속력 값이 격자판을 벗어나는 경우이다.

그림을 그려서 생각해보면 조금 더 이해가 쉽다.

격자판의 왼쪽으로 벗어난 경우

위 그림처럼 파란색 동그라미의 위치에 있는 상어가 왼쪽으로 4칸 이동한다고 생각하면 오른쪽처럼 한번 튕겨나와 3열에 위치하게된다.

왼쪽으로 쭉 4칸 간다고 생각하면 -3열에 위치하게 된다.

다른 경우를 그려보면 규칙을 볼 수 있게 되는데 우선은 위의 경우를 생각해보자.

왼쪽으로 격자판을 벗어나서도 이동하면 -3열이고 최종적으로 3열에 위치하게 된다는 뜻은 이동했을 때 0이하의 값이 나오면 절댓값으로 열을 바꿔주면 최종 위치가 되는 것이다.

즉, x=Math.abs(x); 으로 최종 위치를 결정할 수 있는 것이다.

튕겨서 이동하게 됐으니 상어가 바라보고 있는 방향도 오른쪽으로 바꿔준다.

격자판의 오른쪽으로 벗어난 경우

그렇다면 반대의 경우를 생각해보자. 아까와 같은 위치의 상어가 오른쪽으로 4칸 이동한다고 생각해보면 오른쪽으로 한번 튕겨져 3열에 위치하게 된다.

아까와 같이 오른쪽으로 쭉 이동시켰다고 생각하면 5열에 위치하게 된다.

0보다 작아졌을때와는 다르게 절댓값으로 열의 값을 바꿔준다고 최종 위치가 되는 것이 아니다.

수학적으로 생각해보면 4열 밖으로 넘어간 경우에는 넘어간 만큼 4열에서 그 값을 빼주면 최종 위치가 된다.

즉, 위 경우에서 격자판을 넘어간 횟수는 한 번이다.

4열에서 한 번 튕겨서 3열에 위치하게 되는 것이다.

식을 써보면 (격자판 열의 크기-1)-{(현재위치+이동거리)-(격자판 열의 크기-1)} 이 되고

이를 풀어 써보면 2*C-y-2가 된다.

오른쪽으로 튕겨서 왼쪽을 향하게 됐으니 상어가 바라보는 방향도 왼쪽으로 바꿔준다.

하지만 하나 더 고려해야할 점은 위의 식을 이용하여 튕겨냈는데 튕겨낸 위치도 격자판을 벗어난 경우이다. 이를 해결하기 위해 이동된 위치가 격자판을 벗어났을 때를 조건으로 두어 while문을 반복한다.

위와 같은 방식으로 위,아래로 벗어난 경우를 구해주면 된다.

이동할 자리에 상어가 있는 경우

//이동할 자리에 이미 상어가 있다면 크기가 큰 상어만 넣어주기
if(copy[x][y]!=null){
    if(copy[x][y].z<shark.z){
        copy[x][y]=new Shark(shark.s,tmpD,shark.z);
    }
}else{
    copy[x][y]=new Shark(shark.s,tmpD,shark.z);
}

상어가 이동하게 되면 원래 map 격자판에 넣어주지않고 격자판 크기와 똑같은 빈 배열을 만들어 상어를 하나씩 넣어준다.

그렇게되면 상어가 겹치는 경우를 확실하게 알 수 있게된다.

상어가 겹친다면 크기를 비교하여 더 큰 상어를 위치시키고 아니라면 그냥 해당 상어 정보를 넣어준다.

상어 이동 마무리하기

for(int i=0;i<R;i++){
    for(int j=0;j<C;j++){
        //copy map 에 옮겨주기
        map[i][j]=copy[i][j];
    }
}

위의 과정을 모두 거치고 나면 상어 이동이 완료되었기 때문에 원래 격자판을 update해준다.

낚시왕이 마지막 열까지 도달하여 상어를 잡고 나면 낚시왕이 잡은 상어 크기의 합을 출력해주면 답이 출력된다.

이 문제에서 제일 힘들었던 점은 격자판을 벗어났을 때 위치를 어떻게 지정해줄 것인가였다. 그림을 그리면서 규칙을 찾아내고, 수학적으로 값을 구하려고 하다보니 시간이 꽤 걸렸다.

결국 수학적으로 생각해보면 인덱스를 있었는데 머리를 조금 더 여러 방향으로 써봐야겠다는 생각이 들었다.