[BOJ/Java] 16236. 아기 상어

[BOJ/Java] 16236. 아기 상어

16236번: 아기 상어

---

문제 해석

이 문제에서는 N x N 크기의 격자에 아기 상어와 여러 물고기가 존재하며, 아기 상어는 자신보다 작은 물고기만 먹을 수 있다. 아기 상어는 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가한다. 아기 상어의 목표는 최대한 많은 물고기를 먹는 것이 아니라, 먹을 수 있는 물고기가 없어질 때까지 최단 시간 내에 물고기를 먹는 것이다.

풀이 과정

아기 상어의 이동 경로는 너비 우선 탐색(BFS)를 통해 구현되며, 각 단계에서 가장 가까운 먹을 수 있는 물고기를 찾고 먹는다. 이 과정은 먹을 수 있는 물고기가 없을 때까지 반복된다.

• sol 메소드에서 아기 상어가 더 이상 먹을 수 있는 물고기가 없을 때까지 BFS를 반복적으로 호출한다.
• bfs 메소드는 현재 아기 상어의 위치에서 시작하여 먹을 수 있는 물고기를 찾는다. 가장 가까운 물고기를 찾기 위해 최단 경로를 계산하고, 경로가 같은 물고기가 여러 마리인 경우 가장 위쪽, 그리고 가장 왼쪽에 있는 물고기를 우선적으로 선택한다.
• updateSize 메소드는 아기 상어가 물고기를 먹을 때마다 호출되어 아기 상어의 크기와 먹은 물고기 수를 갱신한다.

코드

package edu.ssafy.im.BOJ.Gold.G3.No16236;

import java.io.*;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {
    private int[][] graph; // 격자 상태 저장 배열
    private final int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 이동 방향 (상하좌우)
    private int size = 2; // 아기 상어의 초기 크기
    private int sizeCount = 0; // 아기 상어가 먹은 물고기 수
    private int ans = 0; // 아기 상어가 먹은 물고기를 먹기까지 걸린 시간
    private boolean[][] visited; // 방문 여부 확인 배열
    Point now; // 아기 상어의 현재 위치

    public static void main(String[] args) throws IOException {
        new Main().io();
    }

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        graph = new int[n][n];

        for (int i = 0; i < graph.length; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < graph.length; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
                if (graph[i][j] == 9) {
                    now = new Point(i, j); // 아기 상어의 초기 위치 설정
                    graph[i][j] = 0; // 아기 상어의 위치를 빈 공간으로 설정
                }
            }
        }
        sol(); // 물고기를 먹는 과정 시작

        sb.append(ans); // 결과 출력
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private void sol() {
        while (true) {
            int time = bfs(); // 가장 가까운 물고기를 찾아 먹는 과정
            if (time != 0) { // 먹은 물고기가 있으면 시간을 더함
                ans += time;
            } else { // 먹을 물고기가 없으면 종료
                break;
            }
        }
    }

    private int bfs() {
        int rx = 0, ry = 0, minTime = Integer.MAX_VALUE;
        visited = new boolean[graph.length][graph.length];
        ArrayDeque<Point> queue = new ArrayDeque<>();
        queue.offer(new Point(now.x, now.y, 0));
        visited[now.x][now.y] = true;

        L:
        while (!queue.isEmpty()) {
            Point pt = queue.poll();
            for (int d = 0; d < direction.length; d++) {
                int nx = pt.x + direction[d][0];
                int ny = pt.y + direction[d][1];
                int nt = pt.time + 1;

                if (nt > minTime) break L; // 더 이상 최단 거리가 아닐 경우 탐색 중단
                if (checkStatus(nx, ny)) { // 이동 가능한 위치인지 확인
                    if (graph[nx][ny] != 0 && graph[nx][ny] < size) { // 먹을 수 있는 물고기가 있는 경우
                        if (nt < minTime) { // 더 가까운 물고기가 발견된 경우
                            rx = nx;
                            ry = ny;
                            minTime = nt;
                        } else if (nt == minTime) { // 거리가 같은 물고기 중에서
                            if (nx < rx || (nx == rx && ny < ry)) { // 가장 위쪽, 가장 왼쪽의 물고기를 선택
                                rx = nx;
                                ry = ny;
                            }
                        }
                    } else {
                        visited[nx][ny] = true;
                        queue.offer(new Point(nx, ny, nt)); // 다음 위치로 이동
                    }
                }
            }
        }

        if (minTime == Integer.MAX_VALUE) { // 먹을 수 있는 물고기가 없는 경우
            return 0;
        } else { // 물고기를 먹은 경우
            graph[rx][ry] = 0;
            now.x = rx;
            now.y = ry;
            updateSize(); // 아기 상어의 크기 갱신
            return minTime;
        }
    }

    private void updateSize() {
        sizeCount++;
        if (size == sizeCount) { // 아기 상어의 크기 증가 조건을 만족하는 경우
            size++;
            sizeCount = 0;
        }
    }

    private boolean checkStatus(int x, int y) {
        return 0 <= x && x < graph.length && 0 <= y && y < graph.length && graph[x][y] <= size && !visited[x][y];
    }

    class Point {
        int x, y, time;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
        public Point(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }
}

시간 복잡도 분석

이 문제의 시간 복잡도는 O(N^2)이다. BFS를 사용하여 각 단계에서 모든 격자를 검사할 수 있으며, 최악의 경우 모든 칸을 검사해야 할 수 있다.

느낀점

이 문제를 통해 시뮬레이션과 BFS의 결합을 통해 복잡한 문제 상황을 해결하는 방법을 배웠다. 특히, 아기 상어의 성장 조건과 이동 규칙을 정확히 구현하는 것이 중요했으며, 이를 통해 다양한 조건을 고려하는 알고리즘 설계 능력을 향상시킬 수 있었다.