BOJ17143_낚시왕

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

문제요약

1. R행 , C열 , r상어의 행 , c상어의 열 , s상어의 속도 , d상어의 방향 , z상어의 크기

2. 1초동안 일어나는 일

- (1) 낚시왕이 오른쪽(열방향)으로 한 칸 이동한다

  (2) 낚시왕이 있는 열에 있는 상어 중에서 땅과 가장 가까운 상어를 잡고 상어가 사라진다. 잡은 상어의 크기가 누적된다.

  (3) 상어가 이동한다.

  (4) 같은 칸에 여러마리의 상어가 있으면 크기가 가장 큰 상어빼고 다 죽는다.

문제issue

1. 상어가 이동하는 부분 구현

- (1) 다차원을 사용??

  (2) list를 사용??

해결흐름

1. 낚시왕이 오른쪽으로 이동하는 부분은 while(man <= C) 동안 반복하게 한다.

2. 땅과 가장 가까운 상어를 잡기 위해서 잡기 전에 Collections.sort를 이용하여 r을 기준으로 sort해주고 man의 위치(열)과 list에 있는 상어의 열을 비교해서 같으면 잡고 크기를 누적한다.

3. 상어가 이동하는 부분은 list에서 r, c, d, s를 가지고 와서 while(s>=1) 동안 반복한다

r과 c를 d(방향)에 맞게 계속 변화 시켜주다가 벽에서 벗어나는 순간 r과 c를 전값으로 돌려주고 s는 유지 되도록 한다. 또한, 방향을 바꿔준다.

4. 같은 칸에 여러마리의 상어가 있는 경우에 크기가 가장 큰 상어빼고 없애기 위해 이차원 배열 size_map , speed_map , dir_map을 만들어서 size_map[r][c] == 0인경우와 != 0인경우로 나눠서 처리해준다.

- (1) size_map[r][c] == 0 인 경우는 size_map[r][c] = 현재size , speed_map[r][c] = 현재speed , dir_map[r][c] = 현재dir을 넣어준다.

  (2) size_map[r][c] != 0 인 경우는 현재size가 더 클때만 넣어준다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
    
    static class shark{
        int r,c,s,d,z;
 
        public shark(int r, int c, int s, int d, int z) {
            this.r = r;
            this.c = c;
            this.s = s;
            this.d = d;
            this.z = z;
        }
 
        public void setR(int r) {
            this.r = r;
        }
 
        public void setC(int c) {
            this.c = c;
        }
 
        public void setD(int d) {
            this.d = d;
        }
    }
    
    private static int[] dr = {0,-1,1,0,0}; // x,위,아래,오,왼
    private static int[] dc = {0,0,0,1,-1};
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim(), " ");
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        List<shark> list = new ArrayList<>();
        
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine().trim(), " ");
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());
            int z = Integer.parseInt(st.nextToken());
            list.add(new shark(r,c,s,d,z));
        }
        
        int man = 0;
        int result = 0;
        while(man <= C) {
            man++;
            Collections.sort(list, new Comparator<shark>() {
                @Override
                public int compare(shark o1, shark o2) {
                    return o1.r - o2.r;
                }
            });
//            System.out.println("=====초기=====");
//            System.out.println("result : " + result);
//            for (int i = 0; i < list.size(); i++) {
//                System.out.println("r : " + list.get(i).r + " c : " + list.get(i).c + " s : " + list.get(i).s + " d : " + list.get(i).d + " z : " + list.get(i).z);
//            }
            // 상어잡기
            for (int i = 0; i < list.size(); i++) {
                if(man == list.get(i).c) {
                    result += list.get(i).z;
                    list.remove(i);
                    break;
                }
            }
//            System.out.println("=====상어사냥 후=====");
//            System.out.println("result : " + result);
//            for (int i = 0; i < list.size(); i++) {
//                System.out.println("r : " + list.get(i).r + " c : " + list.get(i).c + " s : " + list.get(i).s + " d : " + list.get(i).d + " z : " + list.get(i).z);
//            }
            // 상어이동
            for (int i = 0; i < list.size(); i++) {
                int r = list.get(i).r;
                int c = list.get(i).c;
                int speed = list.get(i).s;
                int dir = list.get(i).d;
                while(speed >= 1) {
                    r += dr[dir];
                    c += dc[dir];
                    if(r < 1 || c < 1 || r >= R+1 || c >= C+1) {
                        r -= dr[dir];
                        c -= dc[dir];
                        if(dir==1)
                            dir=2;
                        else if(dir==2)
                            dir=1;
                        else if(dir==3)
                            dir=4;
                        else if(dir==4)
                            dir=3;
                        continue;
                    }
                    speed--;
                }
                list.get(i).setR(r);
                list.get(i).setC(c);
                list.get(i).setD(dir);
            }
//            System.out.println("=====상어이동 후=====");
//            System.out.println("result : " + result);
//            for (int i = 0; i < list.size(); i++) {
//                System.out.println("r : " + list.get(i).r + " c : " + list.get(i).c + " s : " + list.get(i).s + " d : " + list.get(i).d + " z : " + list.get(i).z);
//            }
            // 상어잡아먹기
            int[][] size_map = new int[R+1][C+1];
            int[][] speed_map = new int[R+1][C+1];
            int[][] dir_map = new int[R+1][C+1];
            for (int i = 0; i < list.size(); i++) {
                int r = list.get(i).r;
                int c = list.get(i).c;
                int speed = list.get(i).s;
                int dir = list.get(i).d;
                int size = list.get(i).z;
                if(size_map[r][c] == 0) {
                    size_map[r][c] = size;
                    speed_map[r][c] = speed;
                    dir_map[r][c] = dir;
                }
                else {
                    if(size_map[r][c] < size) {
                        size_map[r][c] = size;
                        speed_map[r][c] = speed;
                        dir_map[r][c] = dir;
                    }
                }
            }
//            for (int i = 0; i < R; i++) {
//                System.out.println(Arrays.toString(size_map[i]));
//            }
//            System.out.println("======================");
            
            list.clear();
            for (int i = 0; i <= R; i++) {
                for (int j = 0; j <= C; j++) {
                    if(size_map[i][j] != 0) {
                        list.add(new shark(i,j,speed_map[i][j],dir_map[i][j],size_map[i][j]));
                    }
                }
            }
//            System.out.println("=====상어먹고 난 후=====");
//            System.out.println("result : " + result);
//            for (int i = 0; i < list.size(); i++) {
//                System.out.println("r : " + list.get(i).r + " c : " + list.get(i).c + " s : " + list.get(i).s + " d : " + list.get(i).d + " z : " + list.get(i).z);
//            }
        } // end of man
        System.out.println(result);
        
        
    } // end of main
} // end of class