본문 바로가기
알고리즘/BFS

[백준] 아기상어 / 자바

by 순원이 2024. 5. 25.

문제         

레벨: 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시간 넘게 붙잡고 있었다. 평상시 어느 공부법이 좋다고는 장담하지 못하겠지만, 가끔 이런 공부법이 반드시 필요하다고 생각이 든다.
저작자표시

'알고리즘 > BFS' 카테고리의 다른 글

[백준 2178] 미로 탐색/ 자바 / bfs  (0) 2024.07.21
[백준 13460] 구슬 탈출2 / 자바 / BFS  (1) 2024.07.03
[백준] 토마토/자바  (0) 2024.05.12
[백준] 벽 부수고 이동하기/자바  (0) 2024.05.07
항해99 26일차 TIl( 단어 변환 / 프로그래머스)  (0) 2024.04.23

관련글

티스토리툴바