[백준 16236] - 아기상어(JAVA)

[문제] 

출처 - https://www.acmicpc.net/problem/16236

16236번: 아기 상어

---

[문제풀이] 

BFS와 구현으로 푸는 문제이다. 구현 문제만 오면 많이 버벅여서 더 많은 연습이 필요 할 것 같다.

https://moonsbeen.tistory.com/231 를 참고하여 문제를 풀었다.

 

맨 처음 상어의 위치를 Queue에 넣어주고 해당 위치를 빈칸으로 만든다.

 

1. BFS탐색을 하여 상어가 먹을 수 있는 물고기 후보들을 List에 담는다.

2. 만약 물고기를 먹을 수 없는 상태면 이동한 거리(시간)를 출력한다.

3. 먹을 수 있는 물고기가 있다면 거리가 제일 작고, 같으면 가장 위를, 같은데 위에 있다면 가장 왼쪽을 선택한다.

4. 선택한 물고기를 먹고 해당 좌표를 0으로 처리하고 답에 이동한 거리를 추가한다.

5. 자신의 크기만큼 물고기를 먹으면 크기가 1증가하고 먹은 물고기 수를 초기화 한다.

6. Queue에 물고기를 먹은 좌표를 넣어 다시 탐색을 시작한다. (1로 되돌아간다)

 

---

[소스코드] 

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

class Node {

    int x;
    int y;
    int dist;

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

public class Main {

    static final int dx[] = {0, 0, 1, -1};
    static final int dy[] = {1, -1, 0, 0};
    static int[][] map;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        Queue<Node> q = new LinkedList<>();
        int n = Integer.parseInt(br.readLine());
        map = new int[n][n];

        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 Node(i, j, 0));
                    map[i][j] = 0;
                }
            }
        }

        int size = 2;
        int eat = 0;
        int ans = 0;
        while (true) {
            ArrayList<Node> eatFish = new ArrayList<>();
            int[][] dist = new int[n][n];

            while (!q.isEmpty()) {
                Node p = q.poll();
                int x = p.x;
                int y = p.y;

                for (int k = 0; k < 4; k++) {
                    int nx = x + dx[k];
                    int ny = y + dy[k];

                    if (0 <= nx && nx < n && 0 <= ny && ny < n) {
                        if (dist[nx][ny] == 0 && map[nx][ny] <= size) {
                            dist[nx][ny] = dist[x][y] + 1;
                            q.add(new Node(nx, ny, dist[nx][ny]));
                            if (1 <= map[nx][ny] && map[nx][ny] <= 6 && map[nx][ny] < size) {
                                eatFish.add(new Node(nx, ny, dist[nx][ny]));
                            }
                        }
                    }
                }
            }

            if (eatFish.size() == 0) {
                System.out.println(ans);
                return;
            }

            Node nowFish = eatFish.get(0);
            for (int i = 1; i < eatFish.size(); i++) {
                if (nowFish.dist > eatFish.get(i).dist) {
                    nowFish = eatFish.get(i);
                } else if (nowFish.dist == eatFish.get(i).dist) {
                    if (nowFish.x > eatFish.get(i).x) {
                        nowFish = eatFish.get(i);
                    } else if (nowFish.x == eatFish.get(i).x) {
                        if (nowFish.y > eatFish.get(i).y) {
                            nowFish = eatFish.get(i);
                        }
                    }
                }
            }
            map[nowFish.x][nowFish.y] = 0;
            ans += nowFish.dist;
            eat++;
            if (size == eat) {
                size++;
                eat = 0;
            }
            q.add(nowFish);

        }

    }

}