문제

풀이 과정

요약

BFS() 활용 문제
처음에는 방문처리를 어떻게 해야하나 고민하다가, 우선 상어에게 가까운 애들을 정렬하여 찾아, 그걸 먹었을때, 이동 거리와 방문거리를 재설정하여 다시 탐색하는 방식으로 진행했다.

먹을 수 있는 물고기를 넣는 우선순위 큐와 맵을 탐색하는 용도의 큐로 나누어 처리한다. 탐색시 먹을 수 있는 물고기의 좌표라면, 우선순위 큐와 큐에 동시에 정보를 넣어준다. 그렇게 큐의 1차 탐색이 모두 끝나면, 이후 pq를 활용하여 지금까지의 먹은 개수, 상어 사이지, 이동거리 등을 일괄계산한다.

상세

먼저 입력을 받는다, 단 탐색의 시작값이 필요하므로, 입력에 9가 나오는 경우의 좌표값을 저장해둔다.

그 다음, 큐와 우선순위 큐를 생성한다. 나의 경우 int[] 을 받도록 했다.

int[0] = r , int[1] = c, int[2] = 상어의 이동거리

방문처릴르 하면서 1차적으로 맵을 모두 탐색한다.
이때 가장 가까이 있는 애들 가운데, 먹을 수 있는 물고기라면 우선순위 큐에 담아주자. 1차 탐색 이후 우선순위 큐에 들어온게 하나도 없다면 이때가 엄마 상어를 불러야 할 때이다. (종료)

우선순위 큐에서는 맨앞에 놓여져 있는 물고기 단 1마리만을 본다. (이후 누적된 물고기들을 방문처리로 인해, 최소거리라 판단할 수 없다.)

이동 거리만큼 ans 에 누적한다. 먹은 물고기 좌표는 빈 곳이니 0으로 돌리고, 다시 탐색이 이루어져야 하므로 큐에 현 좌표를 출발점으로하여 이동거리를 0으로 만든 후 다시 탐색하자.

이 과정이 반복되면 정답이 나온다.

정답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int map[][];
    static final int dr[] = {-1, 0, 1, 0};
    static final int dc[] = {0, -1, 0, 1};
    static int shark_size = 2;
    static int shark_curr_ate = 2;
    static int ans = 0;

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

        Queue<int[]> q = new LinkedList<>();
        boolean visited[][] = new boolean[N][N];
        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) {
										// [0] = r;
										// [1] = c;
										// [2] = dist;
                    q.add(new int[]{i, j, 0});
                    visited[i][j] = true;
                    map[i][j] = 0;
                }
            }
        }

        while (true) {
            PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    if (o1[2] == o2[2]) {
                        if (o1[0] == o2[0]) return o1[1] - o2[1];
                        else return o1[0] - o2[0];
                    } else return o1[2] - o2[2];
                }
            });

            while (!q.isEmpty()) {
                int[] curr = q.poll();
                for (int d = 0; d < 4; d++) {
                    int nr = curr[0] + dr[d];
                    int nc = curr[1] + dc[d];

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

                    if (map[nr][nc] == shark_size || map[nr][nc] == 0) {
                        q.add(new int[]{nr, nc, curr[2] + 1});
                        visited[nr][nc] = true;
                    } else if (map[nr][nc] < shark_size) {
                        pq.add(new int[]{nr, nc, curr[2] + 1});
                        q.add(new int[]{nr, nc, curr[2] + 1});
                        visited[nr][nc] = true;
                    }
                }
            }

            if (pq.isEmpty()) {
                System.out.println(ans);
                return;
            }

            int[] curr = pq.poll();
            if (--shark_curr_ate <= 0) shark_curr_ate = ++shark_size;
            ans += curr[2];
            map[curr[0]][curr[1]] = 0;
            q.add(new int[]{curr[0], curr[1], 0});
            visited = new boolean[N][N];
            visited[curr[0]][curr[1]] = true;
        }
    }
}