[BOJ][Java] 16236. 아기 상어

문제

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

 

문제 이해

• N×N 공간: 빈 칸(0), 물고기(1~6), 상어(9)
• 상어의 크기: 2.
• 상어는 자신의 크기보다 작은 물고기만 먹을 수 있고, 자신의 크기와 같거나 작은 칸은 지나갈 수 있다.
• 가장 가까운 물고기를 먹는다.
  • 거리가 같으면 가장 위(행이 작은) 물고기
  • 그다음 가장 왼쪽(열이 작은) 물고기
• 물고기를 자신의 크기만큼 먹으면 크기가 1 증가
• 더 이상 먹을 수 없을 때까지 이동한 총 시간(=이동 칸 수 합) 을 구한다.

 

아이디어

1. 최단거리 탐색: BFS
2. 거리 → 행 → 열 우선순위: 우선순위 큐

 

구현

상태

• curSize : 현재 상어 크기(초기 2)
• cnt : 현재 크기에서 먹은 물고기 수(크기만큼 먹으면 증가)
• time : 누적 이동 시간
• 방문 배열과 큐는 물고기를 먹을 때마다 초기화
  → 물고기를 먹은 후, 그 자리에서 다음에 먹을 물고기를 탐색하는 것을 반복하기 때문.

 

탐색

• 현재 위치에서 4방향 탐색
  • 격자 밖 / 이미 방문 / 상어보다 큰 물고기가 있는 칸(map[nr][nc] > curSize) 은 건너뛴다.
  • 도착 칸에 먹을 수 있는 물고기가 있으면(0 < map[nr][nc] < curSize), 물고기를 먹는다.
    • 빈 칸으로 갱신: map=0
    • 물고기까지 이동한 시간을 누적: time += cur.time
    • 현재 위치를 그 칸으로 갱신: r = cur.r c = cur.c
    • 먹은 개수 증가: cnt++
  • 만약 현재 크기만큼 물고기를 먹었으면, 크기 증가: if (cnt == curSize) curSize++
• 다음 물고기 탐색
• 우선순위 큐가 빌 때까지 먹은 물고기가 없으면, 더이상 먹을 수 있는 물고기가 없으므로 종료

 

코드

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

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

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

    static int n;
    static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        int curR = 0, curC = 0;

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 9) {
                    curR = i;
                    curC = j;
                    map[i][j] = 0;
                }
            }
        } // 입력 끝

        System.out.println(bfs(curR, curC));
    }

    static int bfs(int r, int c) {
        int time = 0, cnt = 0, curSize = 2; // 총 시간, 먹은 물고기 수, 현재 상어 크기
        int[] dr = { -1, 1, 0, 0 };
        int[] dc = { 0, 0, -1, 1 };

        while (true) {
            PriorityQueue<Point> pq = new PriorityQueue<>(
                    (p1, p2) -> p1.time != p2.time ? Integer.compare(p1.time, p2.time)
                            : (p1.r != p2.r ? Integer.compare(p1.r, p2.r) : Integer.compare(p1.c, p2.c)));
            boolean[][] visited = new boolean[n][n];
            boolean eat = false; // 먹었는지 여부

            pq.offer(new Point(r, c, 0));
            visited[r][c] = true;

            while (!pq.isEmpty()) {
                Point cur = pq.poll();

                if (map[cur.r][cur.c] != 0 && map[cur.r][cur.c] < curSize) { // 물고기 먹을 수 있음
                    map[cur.r][cur.c] = 0;
                    time += cur.time;
                    r = cur.r;
                    c = cur.c;
                    eat = true;
                    cnt++;
                    break;
                }

                for (int i = 0; i < 4; i++) {
                    int nr = cur.r + dr[i];
                    int nc = cur.c + dc[i];

                    if (nr < 0 || nc < 0 || nr >= n || nc >= n || visited[nr][nc] || map[nr][nc] > curSize)
                        continue;

                    pq.offer(new Point(nr, nc, cur.time + 1));
                    visited[nr][nc] = true;
                }

            }

            if (!eat)
                break;

            if (cnt == curSize) {
                cnt = 0;
                curSize++;
            }
        }

        return time;
    }
}