[JAVA]백준 16236번 아기 상어

📌문제 링크

---

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

📌문제 설명

---

이 문제는 BFS를 사용해 상어가 가장 가까운 물고기를 찾아 먹으며 성장하는 과정을 시뮬레이션하는 문제입니다. 상어는 자신보다 작은 물고기만 먹을 수 있으며, 먹은 물고기의 수가 상어의 크기와 같아지면 크기가 증가합니다. 이때, 가장 가까운 물고기를 찾기 위해 BFS를 사용했고, 거리가 같은 물고기가 여러 마리라면 위쪽 → 왼쪽 순으로 우선순위를 적용해 선택했습니다. 상어가 물고기를 먹을 때마다 물고기 위치를 초기화하고, 먹은 물고기 수와 크기를 업데이트하며, 더 이상 먹을 물고기가 없을 때까지 이 과정을 반복합니다.

📌코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

// 아기 상어의 상태를 저장하는 클래스
class comp {
    int x;        // 현재 X 좌표
    int y;        // 현재 Y 좌표
    int time;     // 현재까지 걸린 시간
    int size;     // 상어 크기
    int fishCnt;  // 현재 크기에서 먹은 물고기 수

    public comp(int x, int y, int time, int size, int fishCnt) {
        this.x = x;
        this.y = y;
        this.time = time;
        this.size = size;
        this.fishCnt = fishCnt;
    }
}

// 물고기의 위치 및 거리 정보를 저장하는 클래스
class Pair {
    int x;
    int y;
    int dist; // 거리

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader
    static int N; // 공간의 크기
    static int[][] map = new int[21][21]; // 공간 정보를 저장하는 2차원 배열 (최대 20x20)
    static int[] dx = {1, 0, 0, -1}; // X 좌표 이동 방향 (아래, 왼쪽, 오른쪽, 위)
    static int[] dy = {0, -1, 1, 0}; // Y 좌표 이동 방향
    static Queue<comp> q = new LinkedList<>(); // BFS 탐색을 위한 큐

    public static void main(String[] args) throws Exception {
        input(); // 입력 받기
        solve(); // 문제 해결 (BFS 탐색 시작)
    }

    // 가장 가까운 먹을 수 있는 물고기를 찾는 함수
    public static Pair findFish(int x, int y, int size) {
        Queue<Pair> q = new LinkedList<>(); // BFS 탐색을 위한 큐
        boolean[][] visited = new boolean[21][21]; // 방문 여부 확인 배열
        q.add(new Pair(x, y, 0)); // 현재 상어의 위치를 큐에 추가
        visited[x][y] = true;

        Pair ret = null; // 가장 가까운 물고기 위치
        int minDist = Integer.MAX_VALUE; // 최소 거리 값 초기화

        while (!q.isEmpty()) {
            Pair p = q.poll(); // 큐에서 하나 꺼내기

            // 먹을 수 있는 물고기를 발견한 경우
            if (map[p.x][p.y] > 0 && map[p.x][p.y] < size) {
                if (p.dist < minDist) {
                    minDist = p.dist;
                    ret = p;
                } else if (p.dist == minDist) {
                    // 위쪽에 있는 물고기 우선
                    if (p.x < ret.x || (p.x == ret.x && p.y < ret.y)) {
                        ret = p;
                    }
                }
            }

            // 4방향 탐색
            for (int i = 0; i < 4; i++) {
                int nx = p.x + dx[i];
                int ny = p.y + dy[i];

                // 범위를 벗어나거나, 이미 방문했거나, 상어 크기보다 큰 물고기가 있으면 이동 불가
                if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
                if (visited[nx][ny] || map[nx][ny] > size) continue;

                visited[nx][ny] = true;
                q.add(new Pair(nx, ny, p.dist + 1)); // 이동 거리 +1하여 큐에 추가
            }
        }
        return ret; // 찾은 물고기 반환
    }

    // BFS를 통해 물고기를 먹고 이동하는 과정 실행
    public static void bfs() {
        while (!q.isEmpty()) {
            comp c = q.poll(); // 현재 상어 정보 가져오기
            Pair fish = findFish(c.x, c.y, c.size); // 가장 가까운 물고기 찾기

            if (fish == null) { // 먹을 물고기가 없으면 종료
                System.out.println(c.time);
                return;
            }

            map[fish.x][fish.y] = 0; // 먹은 물고기 위치 초기화

            if (++c.fishCnt == c.size) { // 자신의 크기만큼 물고기를 먹으면 크기 증가
                c.size++;
                c.fishCnt = 0;
            }

            q.add(new comp(fish.x, fish.y, c.time + fish.dist, c.size, c.fishCnt)); // 새로운 상어 상태를 큐에 추가
        }
    }

    // 문제 해결 함수 (BFS 실행)
    public static void solve() {
        bfs();
    }

    // 입력을 처리하는 함수
    public static void input() throws Exception {
        N = Integer.parseInt(br.readLine()); // 공간 크기 입력
        StringTokenizer st;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken()); // 공간 정보 입력

                if (map[i][j] == 9) { // 아기 상어의 위치 발견 시
                    q.add(new comp(i, j, 0, 2, 0)); // 초기 크기 2, 먹은 물고기 수 0으로 설정
                    map[i][j] = 0; // 상어 위치를 빈 칸으로 변경
                }
            }
        }
        br.close(); // 입력 스트림 닫기
    }
}