백준 16236 아기 상어 자바

문제는 다음과 같다.
https://www.acmicpc.net/problem/16236
구현 문제이다.

풀이는 다음과 같다.

import java.io.*;
import java.util.*;

public class Main {
    static int R, C;
    static int[][] map;
    static int answer = 0;
    static int sharkR, sharkC;
    
    static int[] dr = {-1, 1, 0, 0}; //상하좌우
    static int[] dc = {0, 0, -1, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        R = N;
        C = N;
        map = new int[R][C];

        for(int r = 0 ; r < R ; r++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int c = 0 ; c < C ; c++) {
                int a = Integer.parseInt(st.nextToken());
                map[r][c] = a;
                if(a == 9) {
                    sharkR = r;
                    sharkC = c;
                    map[r][c] = 0; //9로 남겨두면 이동 할수잇는데 못해버리는 수가 잇어서 위치만 기록 후 0으로 만들기
                }
            }
        }


        bw.write(String.valueOf(eatFish(new Shark(2, 0, sharkR, sharkC))));
        bw.flush();
        bw.close();

    }
    static int eatFish(Shark s) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        
        for(int r = 0 ; r < R ; r++) {
            for(int c = 0 ; c < C ; c++) {
                if(map[r][c] == 0) continue; //물고기업는곳 빼주고


                if(s.ce(r, c)) { //지금의 상어가 r, c 위치의 물고기를 먹을 수 잇다면 시간 구하고 0보다 크다면 큐에 넣기
                    int t = moveTime(s, r, c);
                    if(t > 0) pq.add(new Node(r, c, t));
                }

                
            }
        }
        
        if(pq.size() != 0) {
            Node nextNode = pq.poll(); //우선순위대로 하나뽑아서
            answer += nextNode.time; //걸린 시간 더해주고
            s.e(nextNode.r, nextNode.c); //해당 위치의 물고기 먹어주며 (크기 먹은 먹이 수 자동 업데이트 된다)
            eatFish(new Shark(s.big, s.eat, nextNode.r, nextNode.c)); //다른 위치로 물고기 먹으러 출발
        }

        //근데 이제 큐 사이즈 0이라면 먹을게 하나도 없으니 끝내기
        return answer;
        
    }
    
    
    
    
    
    static int moveTime(Shark s, int r, int c) { //상어 s 의 r, c까지 이동시간 구하는 매서드. 0 아니면 이동 가능한것
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(s.r, s.c, 0));
        boolean[][] visited = new boolean[R][C];
        visited[s.r][s.c] = true;
        
        while(!q.isEmpty()) {
            Node cN = q.poll();
            int curR = cN.r;
            int curC = cN.c;
            int curT = cN.time;
            
            if(curR == r && curC == c) return curT;
            
            for(int i = 0 ; i < 4 ; i++) {
                int nR = curR + dr[i];
                int nC = curC + dc[i];
                
                if(nR >= 0 && nR < R && nC >= 0 && nC < C && //index 맞고 이동할 수 있으며 방문 안햇다면
                s.cm(nR, nC) && !visited[nR][nC]) {
                    q.add(new Node(nR, nC, curT+1));
                    visited[nR][nC] = true;
                }
            }
        }
        return 0;
    }
    
    
    static class Node implements Comparable<Node> { //이동시 사용할 클래스
        int r, c, time;

        public Node (int r, int c, int time) {
            this.r = r;
            this.c = c;
            this.time = time;
        }

        public int compareTo(Node n) { //걸린 시간, 가장 위, 가장 왼쪽 순
            if(this.time == n.time) {
                if(this.r == n.r) {
                    return this.c - n.c;
                }
                else {
                    return this.r - n.r;
                }
            }
            else {
                return this.time - n.time;
            }
        }
    }




    static class Shark { // 아가상어 클래스
        int big, eat, r, c;
        
        public Shark(int big, int eat, int r, int c) {
            this.big = big;
            this.eat = eat;
            this.r = r;
            this.c = c;
        }
        
        public boolean ce (int r, int c) { //상어가 r c 위치 고기 먹을 수 잇는지
            if(this.big > map[r][c]) return true;
            return false;
        }

        public boolean cm (int r, int c) { //상어가 r c 위치 이동 가능한지
            if(this.big >= map[r][c]) return true;
            return false;
        }
        
        public void e (int r, int c) { //r c 위치 물고기 먹어버리기~
            map[r][c] = 0;
            this.eat++;

            //크기가 2인 아기 상어는 물고기를 2마리 먹으면 크기가 3 + 다시 먹이 0됨
            if(this.eat == this.big) {
                this.big++;
                this.eat = 0;
            }
        }
        
    }

}

• 상어 클래스 : 상어의 위치와 크기, 먹이를 얼마나 먹었는지를 나타내고, 위치의 먹이를 먹을 수 있는지, 위치로 이동할 수 있는지, 먹어버리는 매서드(크기, 먹은 수 조절 한꺼번에)를 가지고 있다.

• 노드 클래스 : 위치와, 해당 노드까지 걸리는 시간을 체크한다. 문제에서 걸리는 시간이 같다면 가장 위, 위도 똑같다면 가장 왼쪽을 선택하라고 했으므로, 정렬에 있어 compareTo를 재정의 해줬다.

• moveTime 매서드 : BFS로, 상어 클래스의 이동 가능 여부 매서드를 사용하여 입력받은 r, c 위치까지의 거리를 체크한다. 큐가 다 돌때까지 이동 거리를 반환하지 못하면, 거기까지 가지 못한다는 소리라서 0을 반환한다.

• eatFish 매서드 : 최종 매서드이다. 공간을 순회하며, 물고기가 있을 시 상어 클래스의 먹을 수 있는지 여부를 체크하는 매서드를 사용하여
  먹을 수 있다면 해당 위치까지의 시간을 체크한다.
  시간을 체크하여 이동 가능 하다면 우선순위 큐에 넣는다.
  그렇게 우선순위 큐를 채우고,
  우선순위 큐의 크기가 0이라면 먹을 물고기가 없으니 매서드를 마친다.
  우선순위 큐의 크기가 0이 아니라면 우선순위대로 하나 뽑고(시간, 위, 왼쪽 우선순위), 상어 클래스의 e 매서드를 사용해 먹어 치운다.
  그다음 다시 eatFish 매서드를 사용해 아기상어는 새로운 여정을 하게 된다. (위치 갱신.)

여기까지가 풀이이다.
위의 내용을 잘 읽어보면, 여러가지 요구사항이 합쳐저 하나의 문제를
해결하는 것이지,
하나하나의 요구사항은 이해하는데 어렵지 않다.
주석과 함께 설명을 읽으면 이해가 더 쉬울 것이다.

한 한시간정도를 투자해서 A4용지에 적고 구현했는데,
테스트케이스가 틀리게 나와서
고민하는데만 30분이 걸렸다.

틀린 부분은,
우선순위를 구현할 때 time, r, c 순서대로 했어야 했는데 time, c, r 순서대로 구현하여 틀렸던 것이었다.
그래서 시간, 왼쪽, 위 우선순위로 구현되니 당연히 틀릴수밖에..

혼자 잘 풀었다고 생각해 뿌듯하기도 했는데, 그런 실수로 시간을 허비해 너무 아쉬웠다.

구현내용을 구상할때만 풀집중을 하는게 아니라,
해당 내용을 작성할때도 집중을 해야한다.

ps. 백번째 포스트이다 화이팅!~!~~!! ㅎㅎ