BOJ_16236 : 아기 상어

👉 문제링크

16236번: 아기 상어

---

---

🔸 문제 분석 🔸

•  N x N 공간에 물고기 M마리와 아기 상어 1마리가 있다.
  • 아기 상어가 최단 거리로 물고기를 모두 먹은 시간을 출력한다.
• 물고기의 수가 맵 정보를 입력받아야 알 수 있으므로 ArrayList에 저장한다.
• 남은 물고기가 여러 마리 일 때 아기 상어는 먹을 수 있는 가장 가까운 물고기를 찾아가는데, 그런 물고기가 여러 마리 일 때는 위쪽, 그 중에서도 왼쪽부터 먹으러 간다.
  • 물고기를 저장 할 때 한 열씩 차례대로 확인했으면 ArrayList 순서대로 확인하면 자동으로 조건에 맞게 된다.
• 아기 상어부터 목표 물고기까지 최단 거리를 계산하기 위해서 BFS를 사용한다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static class Point {
        int r, c;

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

    private static int N, size;
    private static int[][] map;
    private static Point shark, target;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        ArrayList<Point> fish = new ArrayList<>(); // 물고기 위치
        size = 2; // 상어 크기

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int temp = Integer.parseInt(st.nextToken());
                if (temp > 0) {
                    if (temp == 9) { // 상어 처음 위치
                        shark = new Point(i, j);
                        map[i][j] = 0;
                    } else { // 물고기 정보
                        fish.add(new Point(i, j));
                        map[i][j] = temp;
                    }
                }
            }
        }

        // BFS
        int ans = 0;
        int level = 2;
        while (!fish.isEmpty()) {
            int min = N * N;
            int idx = -1;
            for (int i = 0; i < fish.size(); i++) { // 물고기 하나씩 확인
                target = fish.get(i);
                if (map[target.r][target.c] < size) {
                    int cnt = bfs();
                    if (min > cnt) { // 더 가까운 물고기 찾음
                        min = cnt;
                        idx = i;
                    }
                }
            }

            if (idx == -1) break; // 먹을 수 있는 물고기 없음

            // 상어 이동
            shark.r = fish.get(idx).r;
            shark.c = fish.get(idx).c;
            map[shark.r][shark.c] = 0;
            fish.remove(idx);
            if (--level == 0) {
                size++;
                level = size;
            }
            ans += min;
//            print();
        }
        // Output
        System.out.print(ans);
    }

    private static int bfs() {
        Queue<Point> que = new ArrayDeque<>();
        boolean[][] visited = new boolean[N][N];
        que.add(shark);
        visited[shark.r][shark.c] = true;
        int cnt = 0;
        while (!que.isEmpty()) {
            int len = que.size();
            for (int k = 0; k < len; k++) {
                Point now = que.poll();
                if (now.r == target.r && now.c == target.c) return cnt; // 목표 물고기까지 최단 경로 찾음

                for (int j = 0; j < 4; j++) {
                    int r = now.r + dx[j];
                    int c = now.c + dy[j];
                    if (0 <= r && r < N && 0 <= c && c < N && !visited[r][c] && map[r][c] <= size) {
                        visited[r][c] = true;
                        que.add(new Point(r, c));
                    }
                }
            }
            cnt++;
        }
        return N * N;
    }

    private static void print() {
        System.out.println(size);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == shark.r && j == shark.c) sb.append(9);
                else sb.append(map[i][j]);
                sb.append(' ');
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }
}

🔸 코드 해석 🔸

• 처음 맵 정보를 2차원 배열 map에 저장하면서, 물고기 좌표를 ArrayLIst fish에 저장하고, 상어의 위치는 Point shark에 저장한다.
• 물고기가 0마리가 될 때 까지 계산을 반복한다.
  • 모든 물고기를 확인해 먹을 수 있으면 BFS로 최단 경로를 계산해 본다.
  • 먹을 수 있는 물고기가 없으면 반복을 종료한다. (막힌 경우)
  • 최단 거리의 물고기를 찾았으면, 상어를 이동시킨다.
    • 상어 좌표 이동
    • 해당 좌표의 맵은 0 저장
    • 해당 번호의 물고기는 fish에서 삭제
    • 레벨 만큼의 물고기 다 먹었으면 아기 상어 크기 +1, 레벨 재할당
    • 이동 거리 누적
• 최종 이동 거리를 출력한다.

---

🔸 end 🔸

• 아기 상어의 크기가 커지는게 한 마리만 먹으면 커지는 줄 알았는데, 자기 크기만큼의 물고기 수를 먹어야 커지는 것이어서 level 변수를 뒤늦게 추가했다.
• target 물고기를 고를 때 모든 물고기를 탐색해야 하므로 BFS의 장점을 활용하지 못한 것 같다.
  • BFS에서 큐 사이즈 만큼씩 반복해서 계산하는 방법으로, 동시에 최단거리 물고기 리스트를 만들고,
    PriorityQueue를 이용해 좌상단 물고기를 선택할 수 있다.