[백준 17143] 낚시왕 (Java)

 

 

[백준 17143] 낚시왕 (Java)

 

 

17143번: 낚시왕

올해 상반기 삼성전자 SW역량테스트 기출문제다.

 

시뮬레이션으로, 주어진 문제를 잘 읽으면서 코드로 옮겨야 한다.

 

큰 진행 방향은 아래와 같다.

 

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

즉, 낚시왕은 열(C)로 한칸씩 움직이고, 끝까지 가면 종료된다. 이때까지 낚시왕이 잡은 물고기 크기의 합을 출력해주면 되는 문제다.

 

이 문제의 가장 까다로운 부분은 '물고기의 이동'이다. 물고기는 각각 자신의 이동 수, 방향, 크기를 갖고 있기 때문에, 구조체를 이용해서 저장한다면 좀 더 편하게 구현할 수 있을 것 같았다.

 

 

static class Fish implements Comparable<Fish>{
        int r;
        int c;
        int s; // 속력
        int d; // 방향
        int z; // 크기
        
        public Fish(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 setS(int s) {
            this.s = s;
        }
 
        public void setD(int d) {
            this.d = d;
        }
 
        public void setZ(int z) {
            this.z = z;
        }
 
        @Override
        public int compareTo(Fish o) {
            if(this.c == o.c) {
                if(this.r == o.r){
                    return this.z < o.z ? 1 : -1;
                }
                else
                    return this.r < o.r ? -1 : 1;
            }
            return this.c < o.c ? -1 : 1;
        }
        
        
    }

이동한 다음에 list의 해당 값들을 변경해주기 위해 setter를 구현했고, 낚시왕이 가장 가까운 물고기를 잡을 수 있도록 sort를 해주기 위해 comparable의 compareto 메소드를 오버라이드해서 사용했다.

 

진행 수는, 낚시왕이 움직이는 횟수와 일치하므로 이는 열(C)의 값에 해당한다.

 

따라서 C의 수만큼 while문을 돌면서 게임을 진행해주면 된다.

 

여기서는 하나만 더 신중히 생각해주면 된다. 바로 이동 후 같은 행과 열에 위치한 물고기들이 2마리 이상일 때, 크기가 가장 큰 물고기가 나머지 물고기를 잡아먹게 된다. 이때 먹히는 물고기는 낚시왕이 잡은 것이 아니므로 값을 더해주면 안되고, 그냥 list에서 해당 물고기를 삭제시키면서 나아가야 한다.

 

처음에 list의 인덱스 값을 통해 삭제하는 방향으로 구현했는데 예제 테스트케이스는 모두 맞았지만 틀리는 문제로 한참 고민했다. 그래서 그냥 2차원 배열을 따로 만들어, 물고기의 크기 값을 해당 행렬에 넣고, 겹쳤을 때 가장 큰 물고기의 값만 얻을 수 있도록 구현해서 해결할 수 있었다.

 

(다음부터 문제를 풀때는 ArrayList의 index를 이용해 remove하는 건 꼬일 위험이 있기 때문에 값의 비교가 가능할 때 추가적으로 배열을 만들어 해결하도록 하자!)

 

 

전체 소스 코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class Main_17143_낚시왕 {
 
    static class Fish implements Comparable<Fish>{
        int r;
        int c;
        int s; // 속력
        int d; // 방향
        int z; // 크기
        
        public Fish(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 setS(int s) {
            this.s = s;
        }
 
        public void setD(int d) {
            this.d = d;
        }
 
        public void setZ(int z) {
            this.z = z;
        }
 
        @Override
        public int compareTo(Fish o) {
            if(this.c == o.c) {
                if(this.r == o.r){
                    return this.z < o.z ? 1 : -1;
                }
                else
                    return this.r < o.r ? -1 : 1;
            }
            return this.c < o.c ? -1 : 1;
        }
        
        
    }
    
    static int R,C,M;
    static int[][] map;
    static int[][] size;
    static int[][] dir;
    
    static int[] dy = {0,-1,1,0,0}; // 상,하,우,좌
    static int[] dx = {0,0,0,1,-1};
    static ArrayList<Fish> list;
    
    public static void main(String[] args) throws Exception {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        list = new ArrayList<>();
        //물고기의 r,c는 각각 -1해서 넣어줘야함
        
        for (int i = 0; i < M; i++) {
            
            st = new StringTokenizer(br.readLine(), " ");
            
            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 Fish(r-1,c-1,s,d,z));
        }
        
        int time = 0;
        int result = 0; // 잡은 물고기의 합
        
        
        while(time < C) {
            
            Collections.sort(list); // 행 값이 작은 순으로 정렬
            
            // 낚시꾼이 열의 위치가 time인 곳에 있는 가장 가까운 물고기 사냥
            for (int i = 0; i < list.size(); i++) {
                if(list.get(i).c == time){
                    result += list.get(i).z; // 잡은 고기 크기 더함
                    list.remove(i); // 삭제
                    break;
                }
            }
            
            // 물고기 이동
            for (int i = 0; i < list.size(); i++) {
                
                Fish f = list.get(i);
                int r = f.r;
                int c = f.c;
                int dir = f.d;
                int cnt = f.s;
                
                while(cnt > 0) {
                    
                    r+=dy[dir];
                    c+=dx[dir];
                    
                    if(r < 0 || c < 0 || r>=R || c>=C) { // 벽에 만난 순간 (dir 변경)
                        
                        //다시 값 돌려주고
                        r-=dy[dir];
                        c-=dx[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; // cnt 유지한채 한번더 돌리기 위해 continue
                    }
                    
                    cnt--;
                }
                
                list.get(i).setR(r);
                list.get(i).setC(c);
                list.get(i).setD(dir);
                
            }
            
            map = new int[R][C];
            size = new int[R][C];
            dir = new int[R][C];
            
            for (int i = 0; i < list.size(); i++) {
                int r = list.get(i).r;
                int c = list.get(i).c;
                
                if(map[r][c] == 0) {
                    map[r][c] = list.get(i).z;
                    size[r][c] = list.get(i).s;
                    dir[r][c] = list.get(i).d;
                }
                else {
                    if(map[r][c] < list.get(i).z){
                        map[r][c] = list.get(i).z;
                        size[r][c] = list.get(i).s;
                        dir[r][c] = list.get(i).d;
                    }
                }
            }
            
            list.clear();
            
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    if(map[i][j] != 0) {
                        list.add(new Fish(i, j, size[i][j], dir[i][j], map[i][j]));
                    }
                }
            }
            
            
            /*
            System.out.println("------------------------");
            for (int i = 0; i < R; i++) {
                for (int j = 0; j < C; j++) {
                    System.out.print(map[i][j] + " ");
                }
                System.out.println();
            }
            System.out.println("------------------------");
            */
            
            time++;
        }
        
        System.out.println(result);
        
    }
 
}