[알고리즘] BOJ 16236 아기 상어 (JAVA)

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

 

 

백준 골드3 난이도인 문제로, 문제를 읽으면 눈치채기 쉽겠지만 bfs 기반 구현 문제이다.

 

 

가장 가까운 거리를 기반으로 이동하면서, 해당 위치에 있는 물고기를 먹을 수 있는 경우 먹고, 성장까지 해야하므로

 

 

Pos 클래스를 만들어 위치값(x,y)와 출발 지점으로부터의 거리를 저장했고,

 

 

해당 Pos값의 거리를 비교하고 같은 경우 x값, x값도 같은 경우 y값을 비교하여

 

 

 다음에 접근할 위치를 탐색할 수 있도록 클래스를 선언했고, 이를 PriorityQueue를 통해 만족하는 값을 순차적으로 탐색하면서

 

 

만약 현재 위치에 먹을 수 있는 물고기가 있는 경우, 새로운 탐색을 시작해야하므로

 

 

PriorityQueue의 값과 isVisited 배열의 값을 초기화했다.

 

 

import java.io.*;

import java.util.*;

public class boj16236 {

    static int N, M, size, eat_cnt, time;

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

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

    static int water[][];

    static boolean isChecked[][];

    static PriorityQueue<Pos> pq;

    public static void bfs() {

        while (!pq.isEmpty()) {

            Pos cur = pq.poll();

            int x = cur.x;

            int y = cur.y;

            int dist = cur.dist;

            //해당 위치에 물고기를 먹을 수 있는 경우

            if (water[x][y] < size && water[x][y] != 0) {

                water[x][y] = 0;

                time += dist;

                eat_cnt++;

                dist = 0;

                isChecked = new boolean[N][N];

                pq.clear();

            }

            //성장이 가능한 경우

            if (eat_cnt == size) {

                size++;

                eat_cnt = 0;

            }

            for (int idx = 0; idx < 4; idx++) {

                if (isCanMovable(x + dx[idx], y + dy[idx]) && !isChecked[x+dx[idx]][y+dy[idx]]) {

                    pq.add(new Pos(x + dx[idx], y + dy[idx], dist + 1));

                    isChecked[x + dx[idx]][y + dy[idx]] = true;

                }

            }

        }

    }

    public static boolean isCanMovable(int x, int y) {

        if (x >= 0 && x < N && y >= 0 && y < N && water[x][y] <= size) {

            return true;

        }

        return false;

    }

    public static void pre() throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st;

        N = Integer.parseInt(br.readLine());

        size = 2;

        eat_cnt = 0;

        time = 0;

        water = new int[N][N];

        isChecked = new boolean[N][N];

        pq = new PriorityQueue<>();

        for (int i = 0; i < N; i++) {

            st = new StringTokenizer(br.readLine());

            for (int j = 0; j < N; j++) {

                water[i][j] = Integer.parseInt(st.nextToken());

                if (water[i][j] == 9) {

                    water[i][j] = 0;

                    pq.add(new Pos(i, j, 0));

                    isChecked[i][j] = true;

                }

            }

        }

    }

    public static void main(String args[]) throws IOException {

        pre();

        bfs();

        System.out.println(time);

    }

    static class Pos implements Comparable<Pos> {

        int x, y, dist;

        public Pos() {

        }

        public Pos(int x, int y, int dist) {

            this.x = x;

            this.y = y;

            this.dist = dist;

        }

        public int compareTo(Pos o) {

            if (this.dist == o.dist) {

                if (this.x == o.x) {

                    return this.y - o.y;

                }

                return this.x - o.x;

            }

            return this.dist - o.dist;

        }

    }

}

 

 

해당 코드의 실행 시간은 다음과 같다.