[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, startX, startY ;
    private static int[][] fields;

    private static void input() {
        n = inputProcessor.nextInt();
        fields = new int[n + 1][n + 1];

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                int v = inputProcessor.nextInt();

                if(v == 9) {
                    startX = i;
                    startY = j;
                } else if(v > 0) {
                    fields[i][j] = v;
                }
            }
        }
    }

    private static void pro() {
        int scala = 2;
        int ate = 0;
        int sharkX = startX;
        int sharkY = startY;
        int time = 0;
        while(true) {
            int[][] dist = bfs(sharkX, sharkY, scala);
            int[] target = selectOne(dist, scala);

            if(target == null) break;

            sharkX = target[0];
            sharkY = target[1];
            time += dist[sharkX][sharkY];
            ate += 1;
            fields[sharkX][sharkY] = 0;

            if(ate >= scala) {
                scala += 1;
                ate = 0;
            }
        }

        sb.append(time);
    }

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

    private static int[][] bfs(int startX, int startY, int scala) {
        Deque<Integer> que = new ArrayDeque<>(); // multi source bfs
        que.add(startX);
        que.add(startY);

        int[][] dist = new int[n + 1][n + 1];
        for(int i = 1; i <= n; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        dist[startX][startY] = 0;

        while(!que.isEmpty()) {
            int x = que.poll();
            int y = 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(scala < fields[dx][dy]) continue;
                if(dist[dx][dy] != Integer.MAX_VALUE) continue;

                dist[dx][dy] = dist[x][y] + 1;
                que.add(dx);
                que.add(dy);
            }
        }

        return dist;
    }

    private static int[] selectOne(int[][] dist, int scala) {
        int minDist = Integer.MAX_VALUE;
        int x = 0;
        int y = 0;

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(fields[i][j] == 0) continue;
                if(scala <= fields[i][j]) continue;
                if(dist[i][j] == Integer.MAX_VALUE) continue;

                if(dist[i][j] < minDist) {
                    minDist = dist[i][j];
                    x = i;
                    y = j;
                }
            }
        }

        return minDist == Integer.MAX_VALUE
                ? null
                : new int[] {x, y};
    }

    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());
        }
    }
    
}