[백준 16236번] 아기상어 :: 늦깎이 IT

[백준 16236번 아기상어 URL]

1. 종료 조건

- N x N 배열을 모두 탐색했는데도 잡아먹을 수 있는 물고기가 없는 경우

- 탐색을 진행하면서 잡아먹을 수 있는 물고기를 찾지 못했는데 모든 방향이 막혀있는 경우

2. 탐색 조건

- 아기상어의 크기보다 작거나 같을 경우 이동할 수 있다. (아기상어의 크기 >= 물고기의 크기)

3. 비교 조건

 - 아기상어가 잡아먹을 수 있는 물고기를 최초로 만난 경우, 그 물고기를 만나기까지의 이동거리를 저장해야한다.

 - 최초로 물고기를 만났다고 해서 탐색을 종료하는 것이 아니라, 그 이동거리만큼의 모든 위치를 탐색해야한다.

 - 예를 들어, 아래 그림을 보자.

아기상어의 위치로부터 왼쪽에 있는 물고기를 먼저 발견했다고 해서, 바로 그 물고기를 먹은 후에 탐색을 종료하면

안된다. 그 이유는 아기상어의 위쪽에도 크기가 1인 물고기가 있기 때문이다.

즉, 최초로 발견된 물고기까지의 거리를 저장하고, 아기상어의 위치로부터 그 거리만큼 떨어진 곳까지 모두 탐색한

후에, 그 범위내에서 먹을 수 있는 물고기들의 좌표를 저장한다. 그리고 우선순위에 따라 가장 위쪽 혹은 가장 왼쪽에

있는 물고기를 먹어야 한다.

4. 우선순위 큐 활용

2019/02/16 - [알고리즘 이론] - 우선순위 큐와 힙

최소 거리안에 있고, 먹을 수 있는 물고기들은 모두 우선순위 큐에 넣어준다. 우선순위 큐에 넣을 때 정렬 기준은

위쪽으로 올라갈 수록 높고, 왼쪽으로 갈 수록 높은 순서이다.

BFS 탐색을 한 번 끝냈다면, 먹을 수 있는 물고기들의 좌표가 우선순위 큐에 저장되어 있고, 큐의 맨 앞에 있는

데이터가 우리가 원하는 가장 가까운 위치에 있는 물고기이므로 그 물고기를 잡아먹는다.

[코드 분석]

1. searchFish() 메소드를 통해 같은 거리의 먹을 수 있는 물고기들을 찾는다. dist를 매우 큰 값으로 설정한 뒤

최초로 먹을 수 있는 물고기를 찾으면 dist 값을 갱신한다. 이 값은 BFS 탐색을 할 때, 해당 거리(dist) 만큼

벗어나지 않도록 하기 위함이다.

2. solve() 메소드의 while문을 보면 우선순위큐에서 데이터를 하나 꺼내서 아기상어의 위치와 바꿔준다.

아기상어는 자기 크기만큼 물고기를 잡아먹었을 때, 몸집이 커지므로 if문을 통해 해당 조건을 처리한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
 
    public static int N, numOfEat = 0, sharkRow, sharkCol, sharkSize = 2;
    public static int[][] map;
    public static int[] dirX = new int[] { 0, 0, -1, 1 };
    public static int[] dirY = new int[] { -1, 1, 0, 0 };
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static PriorityQueue<Node> priorityQueue = new PriorityQueue<Node>();
 
    public static void main(String[] args) throws Exception {
 
        N = Integer.parseInt(br.readLine());
        priorityQueue = new PriorityQueue<Node>();
        map = new int[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) {
                    sharkRow = i;
                    sharkCol = j;
                }
            }
        }
        System.out.println(solve());
    }
 
    public static void searchFish() {
 
        Queue<Node> q = new LinkedList<Node>();
        boolean[][] visited = new boolean[N][N];
        int dist = Integer.MAX_VALUE;
 
        q.offer(new Node(sharkRow, sharkCol, 0));
        visited[sharkRow][sharkCol] = true;
 
        while (!q.isEmpty()) {
 
            Node node = q.poll();
            int row = node.row;
            int col = node.col;
            int cnt = node.cnt;
 
            for (int i = 0; i < 4; i++) {
 
                int nr = row + dirX[i];
                int nc = col + dirY[i];
 
                if (isBoundary(nr, nc) && !visited[nr][nc] && cnt < dist && map[nr][nc] <= sharkSize) {
 
                    if (map[nr][nc] > 0 && map[nr][nc] < sharkSize) {
 
                        dist = Math.min(dist, cnt + 1);
                        priorityQueue.offer(new Node(nr, nc, cnt + 1));
                        visited[nr][nc] = true;
 
                    } else if (map[nr][nc] == 0 || map[nr][nc] == sharkSize) {
 
                        q.offer(new Node(nr, nc, cnt + 1));
                        visited[nr][nc] = true;
                    }
                }
            }
        }
 
    }
 
    public static int solve() {
 
        int time = 0;
 
        while (true) {
 
            searchFish();
            if (priorityQueue.isEmpty())
                return time;
 
            Node fish = priorityQueue.poll();
            time += fish.cnt;
            map[sharkRow][sharkCol] = 0;
            sharkRow = fish.row;
            sharkCol = fish.col;
            numOfEat += 1;
 
            if (numOfEat == sharkSize) {
                sharkSize += 1;
                numOfEat = 0;
            }
 
            priorityQueue.clear();
 
        }
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < N);
    }
}
 
class Node implements Comparable<Node> {
    int row;
    int col;
    int cnt;
 
    public Node(int row, int col, int cnt) {
        super();
        this.row = row;
        this.col = col;
        this.cnt = cnt;
    }
 
    @Override
    public int compareTo(Node o) {
 
        if (this.row > o.row)
            return 1;
        else if (this.row == o.row) {
            if (this.col > o.col)
                return 1;
            else
                return -1;
        } else {
            return -1;
        }
    }
 
}