백준 - 아기 상어(16236)

오늘 풀어볼 문제는 아기 상어라는 문제이다.

1. 문제요약

• N * N 크기의 공간에 물고리 M마리와 아기 상어 1마리가 있다.
  • 아기상어의 초기 크기는 2이고, 물고기는 입력값으로 주어진다.
• 아기 상어는 자기보다 큰 물고기의 칸은 지나갈 수 없다.
• 아기 상어는 자기와 같은 크기의 물고 칸은 지나갈 수 있다.
• 아기 상어는 자기보다 작은 물고기를 이동과 동시에 먹는다.
  중요포인트 : 자기의 크기와 같은 수의 물고기를 먹어야지만 크기가 1 커진다.

[아기 상어의 움직임]

• 먹을 수 있는 물고기가 여러 마리라면 거리가 가장 가까운 물고기를 먹는다.
  • 거리가 동일하다면, 가장 위에 있는 물고기, 모두 위에 있다면 가장 왼쪽 물고기를 먹는다.
• 거리 측정은 지나가야 하는 칸의 최솟값이다.
• 아기 상어의 이동은 1초 걸린다. (1칸에 1초 걸림.)

더 이상 먹을 수 있는 물고기가 없을 때까지 몇초가 지나는지 구하라.

2. 입출력

[입력]

• 공간의 크기 N(2 ≤ N ≤ 20)
• N개의 줄에 공간의 상태가 주어짐
  • 0: 빈 칸
  • 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
  • 9: 아기 상어의 위치

[출력]

• 더 이상 먹을 수 있는 물고기까지 없을 때 까지. 몇 초가 지났는지 구하라.
  ( = 상어가 얼마나 이동했는지 거리를 구하라. )

3. 알고리즘

• 필요한 전역 자료구조
  - 전체 map 저장할 int 배열 : 입력값으로 주어진 배열
  - 현재 상어의 몸무게, 먹은 물고기 카운팅 전역 변수 선언.

• bfs 시 필요한 자료구조
  - 상어보다 작고, 거리가 같은 물고기들의 위치 정보 모아줄 우선순위 큐
  - 우선순위 큐의 정렬 조건(1. 위쪽인가 3. 왼쪽인가)
  - bfs 돌아줄 ArrayDeque

• 매번 가장 최소 경로 찾는 루트 -> bfs
  - 현재 위치에서 bfs 돌리면서 첫 번째 물고기가 발견됐을 때의 거리 기록
  (이후 해당 거리보다 멀다면 bfs를 돌리지 않기 위함.)
  - 먹을 수 있는 물고기가 발견된다면 우선순위큐에 저장

4. 코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

import javax.print.DocFlavor.READER;


class Info implements Comparable <Info> {
    int x;
    int y;
    int dis;

    public Info (int x, int y, int dis){
        this.x=x;
        this.y=y;
        this.dis = dis;
    }

    @Override
    public int compareTo(Info o) {
        if (this.x == o.x)
            return this.y-o.y;
        return this.x-o.x;
    }
}

public class Main {
    static int N, SHARK_WEIGHT, EAT_CNT, TIME;
    static int [][] MAP;
    static int DIR[][] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        MAP = new int[N][N];

        SHARK_WEIGHT = 2;
        EAT_CNT = 0;
        TIME = 0;

        Info shark = null;
        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){
                    shark = new Info(i, j,0);
                    MAP[i][j] = 0;
                }
            }
        }

        while (shark != null) {
            if(EAT_CNT >= SHARK_WEIGHT) {
                SHARK_WEIGHT++;
                EAT_CNT = 0;
            }
            shark = findFish(shark);
        }
        
        System.out.println(TIME);
    }

    static Info findFish(Info shark) {
        Queue<Info> pq = new PriorityQueue<>();
        Queue<Info> bfs = new ArrayDeque<>();
        boolean [][] visit = new boolean[N][N];

        shark.dis = 0;
        bfs.add(shark);
        visit[shark.x][shark.y] = true;

        int minDis = -1;

        while (!bfs.isEmpty()) {
            Info now = bfs.poll();

            for(int i = 0; i < 4; i++) {
                int nx = now.x+DIR[i][0];
                int ny = now.y+DIR[i][1];

                if(!canGo(nx, ny) || visit[nx][ny]) 
                    continue;
                if(minDis != -1 && now.dis+1 > minDis)
                    continue;
                visit[nx][ny] = true;
                Info next = new Info(nx, ny, now.dis+1);

                if(MAP[nx][ny] > 0 && MAP[nx][ny] < SHARK_WEIGHT){
                    pq.add(next);
                    if(minDis == -1)
                        minDis = next.dis;
                }
                bfs.add(next);
            }
        }

        Info fish = pq.poll();
        if(fish != null){
            EAT_CNT++;
            TIME += fish.dis;
            MAP[fish.x][fish.y] = 0;
        }

        return fish;
    }

    static boolean canGo(int nx, int ny) {
        if(nx < 0 || ny < 0 || nx >= N || ny >= N)
            return false;
        if(MAP[nx][ny] > SHARK_WEIGHT)
            return false;
        return true;
    }
}

한 시간만에 풀어서 뿌듯하다 구현 실력이 올라간 것 같다!!!