[백준] 16236번: 아기 상어 (Java)

문제

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

난이도 : 골드3

알고리즘 : 그래프 탐색, 구현

---

풀이 과정

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어가 상하좌우로 인접한 칸으로 이동하는데 1초가 걸린다. 아기 상어는 자신의 크기 보다 작은 크기의 물고기만 먹을 수 있다. 아기 상어는 가장 가까운 물고기를 먹으려한다. 가장 가까운 물고기가 여러 마리인 경우 가장 위쪽, 가장 왼쪽에 있는 물고기를 먹는다. 아기 상어는 자신의 크기와 같은 수의 물고기를 먹으면 크기가 1 증가한다. 아기 상어가 몇 초 동안 물고기를 먹을 수 있는지 구하는 문제이다.

 

우선, 아기 상어가 먹을 물고기를 찾고 해당 칸으로 이동하는 한 번의 과정을 구현해야 한다. 아기 상어는 가장 가까이 있는 물고기를 먹으므로 최단거리, 즉 BFS를 통해 물고기를 찾을 수 있을 거라 생각했다. 아기 상어의 크기에 비해 작거나 같은 물고기가 있는 칸으로 탐색할 수 있으며, 작은 경우는 먹을 수 있다. 하지만 최단 거리에 여러 물고기가 있을 수 있으므로 처음 찾은 물고기를 바로 먹을 수는 없다. 그러므로 최단 거리에 존재하는 모든 물고기를 찾기 위해 처음 물고기를 찾은 깊이를 모두 탐색하고 가장 위쪽, 가장 왼쪽에 있는 위치를 구한다.

 

먹을 물고기를 찾은 경우 해당 칸을 0으로 변경하고 이동 거리를 총 소요시간에 더해준다. 먹은 물고기의 수도 카운트해서 아기 상어의 크기와 같아지면 아기 상어의 크기를 1 증가시킨다. 이러한 과정을 더 이상 먹을 수 있는 물고기가 없을 때까지 반복하면, 정답을 찾을 수 있다.

 

 

 

---

코드

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

public class Main{
    static int sharkY, sharkX;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] graph = new int[n][n];
        for(int i=0;i<n;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0;j<n;j++){
                int input = Integer.parseInt(st.nextToken());
                if(input == 9) {
                    sharkY = i;
                    sharkX = j;
                    graph[i][j] = 0;
                } else {
                    graph[i][j] = input;
                }
            }
        }

        int count = 0;
        int sharkSize = 2;
        int answer = 0;
        while(true){
            int time = bfs(graph, sharkSize);
            if(time > 0){
                count++;
                answer += time;
            } else {
                break;
            }
            if(count == sharkSize) {
                count = 0;
                sharkSize++;
            }
        }

        System.out.print(answer);
    }

    static int bfs(int[][] graph, int sharkSize){
        Queue<Node> q = new LinkedList<>();
        boolean[][] isVisited = new boolean[graph.length][graph[0].length];
        q.add(new Node(sharkY, sharkX, 0));
        isVisited[sharkY][sharkX] = true;

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

        int depth = 0;
        boolean found = false;
        int fishY = graph.length, fishX = graph[0].length;
        while(!q.isEmpty()){
            Node now = q.poll();
            if(found && depth < now.depth) break;
            if(graph[now.y][now.x] < sharkSize && graph[now.y][now.x] > 0) {
                found = true;
                if(fishY > now.y || (fishY == now.y && fishX > now.x)){
                    fishY = now.y;
                    fishX = now.x;
                }
            }
            depth = now.depth;
            for(int i=0;i<4;i++){
                int newY = now.y + dy[i];
                int newX = now.x + dx[i];

                if(newY < 0 || newY >= graph.length || newX < 0 || newX >= graph[0].length) continue;
                if(isVisited[newY][newX]) continue;
                if(graph[newY][newX] > sharkSize) continue;

                q.add(new Node(newY, newX, now.depth+1));
                isVisited[newY][newX] = true;
            }
        }
        if(fishY != graph.length && fishX != graph[0].length){
            graph[fishY][fishX] = 0;
            sharkY = fishY;
            sharkX = fishX;
            return depth;
        }

        return 0;
    }

    static class Node{
        int y;
        int x;
        int depth;

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