[BOJ16236] 아기 상어 (Java, BFS, 시뮬레이션)

 

문제 링크

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

 

풀이

- 구현(시뮬레이션), BFS 격자형 그래프 탐색 문제 

- BFS와 2중 for문 만으로 충분하게 풀이 가능한 문제

 

요구사항 및 절차 

① 현재 상어 위치에서 잡아 먹을 수 있는 물고기까지의 최단 경로 거리를 구한다 

- 이때 상어의 크기 이상인 물고기가 있는 칸은 지나갈 수 없다 (상어 크기 < 물고기 크기)

- multi source bfs로 최단 거리를 구함 (시간 복잡도 O(V + E))

 

② 최단 거리 정보에서 가장 가까운 물고기 한마리를 선택 (없으면 break문으로 종료)

- 여러 마리인 경우 가장 위에 있는 물고기 중 가장 왼쪽에 있는 물고기를 선택

- 처음에 정렬을 사용하는 방법을 생각했는나, 그럴 필요 없이 2중 for문으로 최단 거리 물고기를 구할 수 있었다

- 이때 물고기의 크기는 상어의 크기보다 작아야 한다 (물고기 크기 < 상어의 크기)

 

③ 상어의 정보를 갱신한다

- 이동 거리 누적, 물고기 시식한 개수, 상어 위치 정보 등

- 이때 상어의 크기만큼 물고기를 먹은 경우 상어의 크기를 갱신한다 

- 예로 상어의 크기 scala = 2이고, 먹은 물고기 수 ate = 2가 되면 상어의 크기는 scale = 3으로 갱신된다 (ate = 0 초기화)

 

 

제출 코드

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

public class Main {
    
    private static StringBuilder sb = new StringBuilder();
    private static InputProcessor inputProcessor = new InputProcessor();

    public static void main(String[] args) {
        input();
        pro();
        output();
    }

    private static int n;
    private static int[][] board;

    private static void input() {
        n = inputProcessor.nextInt();

        board = new int[n + 1][n + 1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                board[i][j] = inputProcessor.nextInt();
            }
        }
    }

    private static void pro() {
        int sharkX = 0;
        int sharkY = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(board[i][j] == 9) {
                    sharkX = i;
                    sharkY = j;
                    break;
                }
            }
        }

        int level = 2; // 상어의 레벨
        int ate = 0; // 현재 먹은 개수
        int timer = 0;

        while(true) {
            List<Fish> fishes = bfs(sharkX, sharkY, level);

            if(fishes.isEmpty()) break;

            Collections.sort(fishes);
            Fish target = fishes.get(0);

            board[sharkX][sharkY] = 0;
            board[target.x][target.y] = 0;
            timer += target.dist;
            sharkX = target.x;
            sharkY = target.y;
            ate += 1;

            if(ate == level) {
                level += 1;
                ate = 0;
            }
        }

        sb.append(timer);
    }

    private static final int[][] dir = {
            {0, 1},
            {1, 0},
            {-1, 0},
            {0, -1}
    };

    private static List<Fish> bfs(int startX, int startY, int level) {
        List<Fish> fishes = new ArrayList<>();
        
        Deque<Integer> que = new ArrayDeque<>(); // multi source bfs
        que.add(startX);
        que.add(startY);
        que.add(0);

        boolean[][] visited = new boolean[n + 1][n + 1];
        visited[startX][startY] = true;

        while(!que.isEmpty()) {
            int x = que.poll();
            int y = que.poll();
            int dist = que.poll();

            for(int i = 0; i < 4; i++) {
                int dx = x + dir[i][0];
                int dy = y + dir[i][1];

                if(dx < 1 || dy < 1 || dx > n || dy > n) continue;
                if(visited[dx][dy]) continue;
                if(board[dx][dy] > level) continue;

                if(board[dx][dy] != 0 && board[dx][dy] < level) {
                    fishes.add(new Fish(dx, dy, dist + 1));
                }

                visited[dx][dy] = true;
                que.add(dx);
                que.add(dy);
                que.add(dist + 1);
            }
        }

        return fishes;
    }

    private static class Fish implements Comparable<Fish>{
        private int x;
        private int y;
        private int dist;

        public Fish(int x, int y, int dist) {
            this.x = x;
            this.y = y;
            this.dist = dist;
        }

        @Override
        public int compareTo(Fish o) {
            if(this.dist != o.dist) {
                return this.dist - o.dist;
            } else if(this.x == o.x) {
                return this.y - o.y;
            }

            return this.x - o.x;
        }
    }

    private static void output() {
        try (BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            bw.write(sb.toString());
            bw.flush();
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }

    private static class InputProcessor {
        private BufferedReader br;
        private StringTokenizer st;

        public InputProcessor() {
            this.br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return st.nextToken();
        }

        public String nextLine() {
            String result = "";

            try {
                result = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }

            return result;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }
    }
    
}