[백준] 아기상어 / 자바

문제         

레벨: G3
알고리즘: 
풀이시간: 12:34
힌트 참조 유무:

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

1 번째 시도: 실패   

[알고리즘 선택 사고 과정]

• 먹을 수 있는 것들을 다 먹어야 함(배열 탐색)
• 먹을 수 있는 것에서 갈 때에는 최소한의 거리로 가야 함 -> BFS 선택
• 되게 간단히 알고리즘 선택했다

 

[풀이 과정]

• 반복문
  • 상어가 먹을 수 있는 것을 찾을 때까지 탐색(BFS)한다.
• 만약 먹을 것이 없다면 반복문을 종료하고 답을 반환한다.
• 자세한 건 주석 참조  

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int[][] arr;
    static int sharkSize = 2;
    static int ans = 0;
    static Pos sharkInd;
    static int[] dirX = {1, 0, 0, -1};
    static int[] dirY = {0, 1, -1, 0};
    static int N;
    static int eating = 0;

    public static void main(String[] args) throws IOException {
        LinkedList<Integer> ll = new LinkedList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];

        //배열 입력받기
        for (int i = 0; i < N; i++) {
            String[] s1 = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(s1[j]);
                //먹이와 샤크 위치 저장
                if (arr[i][j] != 0) {
                    if (arr[i][j] == 9)
                        sharkInd = new Pos(j, i,0);
                }
            }
        }

       while(true) {
//           System.out.println("Bfs");
           boolean canEat = bfs();
           if(canEat == false)
               break;
       }

        System.out.println(ans);
    }

    public static boolean bfs() {
        boolean visited[][] = new boolean[N][N];
        Queue<Pos> q = new ArrayDeque<>();
        boolean canEat = false;

        visited[sharkInd.y][sharkInd.x] = true;
        q.add(sharkInd);
        while (!q.isEmpty()) {
            Pos poll = q.poll();
            int x = poll.x;
            int y = poll.y;
            int cnt = poll.cnt;

            //상어가 먹을 수 있을 경우
            if(arr[y][x] != 0 && sharkSize > arr[y][x]) {
//                System.out.println("eat");
                arr[y][x] = 0;
                eating++;
                ans += cnt;
                sharkInd = new Pos(x,y,0);
                if(eating == sharkSize) {
                    sharkSize++;
                    eating = 0;
                }
                canEat = true;
                return canEat;
            }

            //우,하,상,좌 탐색
            for (int i = 0; i < 4; i++) {
                int nx = x + dirX[i];
                int ny = y + dirY[i];
                if (nx < 0 || nx >= N || ny <0 || ny >= N)
                    continue;
                if(arr[ny][nx] > sharkSize || visited[ny][nx])
                    continue;
                visited[ny][nx] = true;
                q.add(new Pos(nx,ny, cnt+1));
            }
        }

        return canEat;
    }

    public static class Pos {
        int x;
        int y;
        int cnt;
        public Pos(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
}

[결과]

• 실패!
• 예제 1,2,3번은 맞게 출력 되었지만, 예제 4,5,6은 답과 다르게 나왔다.

[실패 원인]

• "거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다" 라는 조건을 빼먹고 구현했다.
• 상어가 먹이를 먹고 나서 처음 상어의 위치와 먹은 위치의 숫자들을 안 바꿔줬다

 

[해결방안]

• 큐 탐색 우,하,상,좌 순에서 -> 하, 좌, 우, 상 순으로 하기
• 처음 상어 위치 0으로 바꾸고 먹은 위치 9로 바꾸기

2 번째 시도: 실패  

• 결과 먼저 말씀드리자면 틀렸다. 
• sout를 찍어 탐색 과정을 보여드리겠다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static int[][] arr;
    static int sharkSize = 2;
    static int ans = 0;
    static Pos sharkInd;
    static int[] dirX = {0, -1, 1, 0};
    static int[] dirY = {-1, 0, 0, 1};
    static int N;
    static int eating = 0;

    public static void main(String[] args) throws IOException {
        LinkedList<Integer> ll = new LinkedList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];

        //배열 입력받기
        for (int i = 0; i < N; i++) {
            String[] s1 = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(s1[j]);
                //먹이와 샤크 위치 저장
                if (arr[i][j] != 0) {
                    if (arr[i][j] == 9)
                        sharkInd = new Pos(j, i, 0);
                }
            }
        }

        while (bfs()) {
            if (eating == sharkSize) {
                sharkSize++;
                eating = 0;
            }
        }

        System.out.println(ans);
    }

    public static boolean bfs() {
        boolean visited[][] = new boolean[N][N];
        Queue<Pos> q = new ArrayDeque<>();
        boolean canEat = false;

        arr[sharkInd.y][sharkInd.x] = 0;
        visited[sharkInd.y][sharkInd.x] = true;
        q.add(sharkInd);
        while (!q.isEmpty()) {
            Pos poll = q.poll();
            int x = poll.x;
            int y = poll.y;
            int cnt = poll.cnt;

            //상어가 먹을 수 있을 경우
            if (arr[y][x] != 0 && sharkSize > arr[y][x]) {
                System.out.println("eat: " + arr[y][x]);
                arr[y][x] = 0;
                eating++;
                ans += cnt;
                sharkInd = new Pos(x, y, 0);
                arr[sharkInd.y][sharkInd.x] = 9;

                System.out.println("sharksize: " + sharkSize);
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        System.out.print(arr[i][j] + " ");
                    }
                    System.out.println();
                }
                System.out.println();
                canEat = true;
                return canEat;
            }

            //우,하,상,좌 탐색
            for (int i = 0; i < 4; i++) {
                int nx = x + dirX[i];
                int ny = y + dirY[i];
                if (nx < 0 || nx >= N || ny < 0 || ny >= N)
                    continue;
                if (arr[ny][nx] > sharkSize || visited[ny][nx])
                    continue;
                visited[ny][nx] = true;
                q.add(new Pos(nx, ny, cnt + 1));
            }
        }

        return canEat;
    }

    public static class Pos {
        int x;
        int y;
        int cnt;

        public Pos(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }
}

 

"C:\Program Files\Java\jdk-17\bin\java.exe" "-javaagent:C:\Program Files\JetBrains\IntelliJ IDEA 2023.1.1\lib\idea_rt.jar=2321:C:\Program Files\JetBrains\IntelliJ IDEA 2023.1.1\bin" -Dfile.encoding=UTF-8 -classpath C:\Users\User\Desktop\Java코드\java-pratice\out\production\java-pratice Main
6
5 4 3 2 3 4
4 3 2 3 4 5
3 2 9 5 6 6
2 1 2 3 4 5
3 2 1 6 5 4
6 6 6 6 6 6

eat: 1
sharksize: 2
5 4 3 2 3 4 
4 3 2 3 4 5 
3 2 0 5 6 6 
2 9 2 3 4 5 
3 2 1 6 5 4 
6 6 6 6 6 6 

eat: 1
sharksize: 2
5 4 3 2 3 4 
4 3 2 3 4 5 
3 2 0 5 6 6 
2 0 2 3 4 5 
3 2 9 6 5 4 
6 6 6 6 6 6 

eat: 2
sharksize: 3
5 4 3 2 3 4 
4 3 2 3 4 5 
3 2 0 5 6 6 
2 0 9 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 2
sharksize: 3
5 4 3 2 3 4 
4 3 9 3 4 5 
3 2 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 2
sharksize: 3
5 4 3 9 3 4 
4 3 0 3 4 5 
3 2 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 3
sharksize: 4
5 4 9 0 3 4 
4 3 0 3 4 5 
3 2 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 3
sharksize: 4
5 4 0 0 3 4                                                
4 9 0 3 4 5                        <========= 요 단계에서 틀렸다.
3 2 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 2
sharksize: 4
5 4 0 0 3 4 
4 0 0 3 4 5 
3 9 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 3
sharksize: 4
5 4 0 0 3 4 
4 0 0 3 4 5 
9 0 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 4
sharksize: 5
5 4 0 0 3 4 
9 0 0 3 4 5 
0 0 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 4
sharksize: 5
5 9 0 0 3 4 
0 0 0 3 4 5 
0 0 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 3
sharksize: 5
5 0 0 0 9 4 
0 0 0 3 4 5 
0 0 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 4
sharksize: 5
5 0 0 0 0 9 
0 0 0 3 4 5 
0 0 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 4
sharksize: 5
5 0 0 0 0 0 
0 0 0 3 9 5 
0 0 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 3
sharksize: 6
5 0 0 0 0 0 
0 0 0 9 0 5 
0 0 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 5
sharksize: 6
5 0 0 0 0 0 
0 0 0 0 0 5 
0 0 0 9 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 3
sharksize: 6
5 0 0 0 0 0 
0 0 0 0 0 5 
0 0 0 0 6 6 
2 0 0 9 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 4
sharksize: 6
5 0 0 0 0 0 
0 0 0 0 0 5 
0 0 0 0 6 6 
2 0 0 0 9 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 5
sharksize: 6
5 0 0 0 0 0 
0 0 0 0 0 5 
0 0 0 0 6 6 
2 0 0 0 0 9 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 4
sharksize: 6
5 0 0 0 0 0 
0 0 0 0 0 5 
0 0 0 0 6 6 
2 0 0 0 0 0 
3 2 0 6 5 9 
6 6 6 6 6 6 

eat: 5
sharksize: 7
5 0 0 0 0 0 
0 0 0 0 0 5 
0 0 0 0 6 6 
2 0 0 0 0 0 
3 2 0 6 9 0 
6 6 6 6 6 6 

eat: 6
sharksize: 7
5 0 0 0 0 0 
0 0 0 0 0 5 
0 0 0 0 6 6 
2 0 0 0 0 0 
3 2 0 9 0 0 
6 6 6 6 6 6 

eat: 6
sharksize: 7
5 0 0 0 0 0 
0 0 0 0 0 5 
0 0 0 0 6 6 
2 0 0 0 0 0 
3 2 0 0 0 0 
6 6 6 9 6 6 

eat: 6
sharksize: 7
5 0 0 0 0 0 
0 0 0 0 0 5 
0 0 0 0 6 6 
2 0 0 0 0 0 
3 2 0 0 0 0 
6 6 9 0 6 6 

eat: 6
sharksize: 7
5 0 0 0 0 0 
0 0 0 0 0 5 
0 0 0 0 6 6 
2 0 0 0 0 0 
3 2 0 0 0 0 
6 9 0 0 6 6 

eat: 2
sharksize: 7
5 0 0 0 0 0 
0 0 0 0 0 5 
0 0 0 0 6 6 
2 0 0 0 0 0 
3 9 0 0 0 0 
6 0 0 0 6 6 

eat: 3
sharksize: 7
5 0 0 0 0 0 
0 0 0 0 0 5 
0 0 0 0 6 6 
2 0 0 0 0 0 
9 0 0 0 0 0 
6 0 0 0 6 6 

eat: 2
sharksize: 8
5 0 0 0 0 0 
0 0 0 0 0 5 
0 0 0 0 6 6 
9 0 0 0 0 0 
0 0 0 0 0 0 
6 0 0 0 6 6 

eat: 6
sharksize: 8
5 0 0 0 0 0 
0 0 0 0 0 5 
0 0 0 0 6 6 
0 0 0 0 0 0 
0 0 0 0 0 0 
9 0 0 0 6 6 

eat: 6
sharksize: 8
5 0 0 0 0 0 
0 0 0 0 0 5 
0 0 0 0 6 6 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 9 6 

eat: 6
sharksize: 8
5 0 0 0 0 0 
0 0 0 0 0 5 
0 0 0 0 6 6 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 9 

eat: 6
sharksize: 8
5 0 0 0 0 0 
0 0 0 0 0 5 
0 0 0 0 6 9 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 

eat: 5
sharksize: 8
5 0 0 0 0 0 
0 0 0 0 0 9 
0 0 0 0 6 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 

eat: 6
sharksize: 8
5 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 9 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 

eat: 5
sharksize: 8
9 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 

56

Process finished with exit code 0

[실패원인]

• 큐 탐색 우,하,상,좌 순에서 -> 하, 좌, 우, 상 순으로 바꾸더라도 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 찾지 못한다.

 

[해결볍]

• BFS 탐색에서 모든 후보지를 수집한 후, 정렬하여 우선순위가 가장 높은 먹이를 선택하는 방법이 필요합니다.

 

 

3 번째 시도 : 성공 

 

sout.ver

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class Main {
    static int[][] arr;
    static int sharkSize = 2;
    static int ans = 0;
    static Pos sharkInd;
    static int[] dirX = {0, -1, 1, 0};
    static int[] dirY = {-1, 0, 0, 1};
    static int N;
    static int eating = 0;

    public static void main(String[] args) throws IOException {
        LinkedList<Integer> ll = new LinkedList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];

        //배열 입력받기
        for (int i = 0; i < N; i++) {
            String[] s1 = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(s1[j]);
                //먹이와 샤크 위치 저장
                if (arr[i][j] != 0) {
                    if (arr[i][j] == 9)
                        sharkInd = new Pos(j, i, 0);
                }
            }
        }

        while (bfs()) {
            if (eating == sharkSize) {
                sharkSize++;
                eating = 0;
            }
        }

        System.out.println(ans);
    }

    public static boolean bfs() {
        boolean visited[][] = new boolean[N][N];
        PriorityQueue<Pos> pq = new PriorityQueue<>();
        boolean canEat = false;

        arr[sharkInd.y][sharkInd.x] = 0;
        visited[sharkInd.y][sharkInd.x] = true;
        pq.add(sharkInd);
        while (!pq.isEmpty()) {
            Pos poll = pq.poll();
            int x = poll.x;
            int y = poll.y;
            int cnt = poll.cnt;

            //상어가 먹을 수 있을 경우
            if (arr[y][x] != 0 && sharkSize > arr[y][x]) {
                System.out.println("eat: " + arr[y][x]);
                arr[y][x] = 0;
                eating++;
                ans += cnt;
                sharkInd = new Pos(x, y, 0);
                arr[sharkInd.y][sharkInd.x] = 9;

                System.out.println("sharksize: " + sharkSize);
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        System.out.print(arr[i][j] + " ");
                    }
                    System.out.println();
                }
                System.out.println();
                canEat = true;
                return canEat;
            }

            //우,하,상,좌 탐색
            for (int i = 0; i < 4; i++) {
                int nx = x + dirX[i];
                int ny = y + dirY[i];
                if (nx < 0 || nx >= N || ny < 0 || ny >= N)
                    continue;
                if (arr[ny][nx] > sharkSize || visited[ny][nx])
                    continue;
                visited[ny][nx] = true;
                pq.add(new Pos(nx, ny, cnt + 1));
            }
        }

        return canEat;
    }

    public static class Pos implements Comparable<Pos>{
        int x;
        int y;
        int cnt;

        public Pos(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }

        @Override
        public int compareTo(Pos o) {
            if (o.cnt != cnt){
                return cnt - o.cnt;
            } else if (o.y != y) {
                return y - o.y;
            }
            else {// distance same, x same
                return x - o.x;
            }
        }
    }
}

"C:\Program Files\Java\jdk-17\bin\java.exe" "-javaagent:C:\Program Files\JetBrains\IntelliJ IDEA 2023.1.1\lib\idea_rt.jar=2449:C:\Program Files\JetBrains\IntelliJ IDEA 2023.1.1\bin" -Dfile.encoding=UTF-8 -classpath C:\Users\User\Desktop\Java코드\java-pratice\out\production\java-pratice Main
6
5 4 3 2 3 4
4 3 2 3 4 5
3 2 9 5 6 6
2 1 2 3 4 5
3 2 1 6 5 4
6 6 6 6 6 6
eat: 1
sharksize: 2
5 4 3 2 3 4 
4 3 2 3 4 5 
3 2 0 5 6 6 
2 9 2 3 4 5 
3 2 1 6 5 4 
6 6 6 6 6 6 

eat: 1
sharksize: 2
5 4 3 2 3 4 
4 3 2 3 4 5 
3 2 0 5 6 6 
2 0 2 3 4 5 
3 2 9 6 5 4 
6 6 6 6 6 6 

eat: 2
sharksize: 3
5 4 3 2 3 4 
4 3 2 3 4 5 
3 2 0 5 6 6 
2 0 9 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 2
sharksize: 3
5 4 3 2 3 4 
4 3 9 3 4 5 
3 2 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 2
sharksize: 3
5 4 3 9 3 4 
4 3 0 3 4 5 
3 2 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 3
sharksize: 4
5 4 9 0 3 4 
4 3 0 3 4 5 
3 2 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 3
sharksize: 4
5 4 0 0 9 4 
4 3 0 3 4 5 
3 2 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 3
sharksize: 4
5 4 0 0 0 4 
4 3 0 9 4 5 
3 2 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 3
sharksize: 4
5 4 0 0 0 4 
4 9 0 0 4 5 
3 2 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 4
sharksize: 5
5 9 0 0 0 4 
4 0 0 0 4 5 
3 2 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 4
sharksize: 5
5 0 0 0 0 4 
9 0 0 0 4 5 
3 2 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 3
sharksize: 5
5 0 0 0 0 4 
0 0 0 0 4 5 
9 2 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 2
sharksize: 5
5 0 0 0 0 4 
0 0 0 0 4 5 
0 9 0 5 6 6 
2 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 2
sharksize: 5
5 0 0 0 0 4 
0 0 0 0 4 5 
0 0 0 5 6 6 
9 0 0 3 4 5 
3 2 0 6 5 4 
6 6 6 6 6 6 

eat: 3
sharksize: 6
5 0 0 0 0 4 
0 0 0 0 4 5 
0 0 0 5 6 6 
0 0 0 3 4 5 
9 2 0 6 5 4 
6 6 6 6 6 6 

eat: 2
sharksize: 6
5 0 0 0 0 4 
0 0 0 0 4 5 
0 0 0 5 6 6 
0 0 0 3 4 5 
0 9 0 6 5 4 
6 6 6 6 6 6 

eat: 3
sharksize: 6
5 0 0 0 0 4 
0 0 0 0 4 5 
0 0 0 5 6 6 
0 0 0 9 4 5 
0 0 0 6 5 4 
6 6 6 6 6 6 

eat: 5
sharksize: 6
5 0 0 0 0 4 
0 0 0 0 4 5 
0 0 0 9 6 6 
0 0 0 0 4 5 
0 0 0 6 5 4 
6 6 6 6 6 6 

eat: 4
sharksize: 6
5 0 0 0 0 4 
0 0 0 0 9 5 
0 0 0 0 6 6 
0 0 0 0 4 5 
0 0 0 6 5 4 
6 6 6 6 6 6 

eat: 5
sharksize: 6
5 0 0 0 0 4 
0 0 0 0 0 9 
0 0 0 0 6 6 
0 0 0 0 4 5 
0 0 0 6 5 4 
6 6 6 6 6 6 

eat: 4
sharksize: 7
5 0 0 0 0 9 
0 0 0 0 0 0 
0 0 0 0 6 6 
0 0 0 0 4 5 
0 0 0 6 5 4 
6 6 6 6 6 6 

eat: 6
sharksize: 7
5 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 6 9 
0 0 0 0 4 5 
0 0 0 6 5 4 
6 6 6 6 6 6 

eat: 6
sharksize: 7
5 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 9 0 
0 0 0 0 4 5 
0 0 0 6 5 4 
6 6 6 6 6 6 

eat: 4
sharksize: 7
5 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 9 5 
0 0 0 6 5 4 
6 6 6 6 6 6 

eat: 5
sharksize: 7
5 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 9 
0 0 0 6 5 4 
6 6 6 6 6 6 

eat: 4
sharksize: 7
5 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 6 5 9 
6 6 6 6 6 6 

eat: 5
sharksize: 7
5 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 6 9 0 
6 6 6 6 6 6 

eat: 6
sharksize: 8
5 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 9 0 0 
6 6 6 6 6 6 

eat: 6
sharksize: 8
5 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
6 6 6 9 6 6 

eat: 6
sharksize: 8
5 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
6 6 9 0 6 6 

eat: 6
sharksize: 8
5 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
6 9 0 0 6 6 

eat: 6
sharksize: 8
5 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
9 0 0 0 6 6 

eat: 6
sharksize: 8
5 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 9 6 

eat: 6
sharksize: 8
5 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 9 

eat: 5
sharksize: 8
9 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 

60

Process finished with exit code 0

 

sout 없는 버전 / 정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class Main {
    static int[][] arr;
    static int sharkSize = 2;
    static int ans = 0;
    static Pos sharkInd;
    static int[] dirX = {0, -1, 1, 0};
    static int[] dirY = {-1, 0, 0, 1};
    static int N;
    static int eating = 0;

    public static void main(String[] args) throws IOException {
        LinkedList<Integer> ll = new LinkedList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = new int[N][N];

        //배열 입력받기
        for (int i = 0; i < N; i++) {
            String[] s1 = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(s1[j]);
                //먹이와 샤크 위치 저장
                if (arr[i][j] != 0) {
                    if (arr[i][j] == 9)
                        sharkInd = new Pos(j, i, 0);
                }
            }
        }

        while (bfs()) {
            if (eating == sharkSize) {
                sharkSize++;
                eating = 0;
            }
        }

        System.out.println(ans);
    }

    public static boolean bfs() {
        boolean visited[][] = new boolean[N][N];
        PriorityQueue<Pos> pq = new PriorityQueue<>();
        boolean canEat = false;

        arr[sharkInd.y][sharkInd.x] = 0;
        visited[sharkInd.y][sharkInd.x] = true;
        pq.add(sharkInd);
        while (!pq.isEmpty()) {
            Pos poll = pq.poll();
            int x = poll.x;
            int y = poll.y;
            int cnt = poll.cnt;

            //상어가 먹을 수 있을 경우
            if (arr[y][x] != 0 && sharkSize > arr[y][x]) {
                System.out.println("eat: " + arr[y][x]);
                arr[y][x] = 0;
                eating++;
                ans += cnt;
                sharkInd = new Pos(x, y, 0);
                arr[sharkInd.y][sharkInd.x] = 9;
                canEat = true;
                return canEat;
            }

            //우,하,상,좌 탐색
            for (int i = 0; i < 4; i++) {
                int nx = x + dirX[i];
                int ny = y + dirY[i];
                if (nx < 0 || nx >= N || ny < 0 || ny >= N)
                    continue;
                if (arr[ny][nx] > sharkSize || visited[ny][nx])
                    continue;
                visited[ny][nx] = true;
                pq.add(new Pos(nx, ny, cnt + 1));
            }
        }

        return canEat;
    }

    public static class Pos implements Comparable<Pos>{
        int x;
        int y;
        int cnt;

        public Pos(int x, int y, int cnt) {
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }

        @Override
        public int compareTo(Pos o) {
            if (o.cnt != cnt){
                return cnt - o.cnt;
            } else if (o.y != y) {
                return y - o.y;
            }
            else {// distance same, x same
                return x - o.x;
            }
        }
    }
}

 

 

 

배운 점   

• BFS + 우선순위 큐 활용법
• 평상시 1시간이 지나면 공부 효율을 위해 정답코드를 보며 공부해왔다. 오늘은 오기가 붙어 2시간 넘게 붙잡고 있었다. 평상시 어느 공부법이 좋다고는 장담하지 못하겠지만, 가끔 이런 공부법이 반드시 필요하다고 생각이 든다.