백준 16236번 : 아기 상어 java

이 문제는 bfs를 이용해서 아기 상어가 엄마 상어에게 도움을 받지 않고 얼마나 물고기를 먹으러 이동할 수 있는지를
구하는 문제입니다.

이 문제의 초기 조건은 아래와 같습니다.

---

아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.

아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.

---

 

여기서 아기 상어가 상하좌우로 1칸씩 이동할 수 있다는 것에서 bfs를 사용할 수 있을 것이라는 생각을 했습니다.

그리고 아래의 조건들은 아기 상어가 이동할 때의 조건입니다.

 

---

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야 하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

---

여기서 아기 상어가 먹을 수 있는 물고기가 많다면 가장 윗 줄에 있는 물고기, 그리고 같은 줄에 있다면 가장 왼쪽의
물고기를 먹는다는 사실을 알 수 있습니다.

따라서 아기 상어에서부터 걸리는 시간이 같은지를 확인하는 minTime 변수와 같은 시간이 걸리는 물고기 들 중에서
가장 윗 줄에 있는지 확인하는 minRow 변수와 row가 같을 때 가장 왼쪽에 위치하고 있는지 확인하는 minCol 변수가
필요하다는 것을 알 수 있습니다.

이러한 조건들을 신경 써주시면서 bfs를 사용하시면 이 문제를 해결할 수 있습니다.

이제 코드를 보여드리도록 하겠습니다.

---

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

public class Main {
    static int N, sharkRow, sharkCol, sharkSize = 2, time, eatCount = 0;
    static int[][] map;
    static int[] dR = {1, -1, 0, 0};
    static int[] dC = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        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;

                    map[i][j] = 0;
                }
            }
        }

        int timeSum = 0;
        //부모가 옮기지 않아도 될 때 계속 반복
        while(sharkGo())
            timeSum += time;

        System.out.println(timeSum);
    }

    static boolean sharkGo(){
        time = 0;
        //먹은 물고기의 수가 몸의 크기와 같아지면 몸의 크기 증가
        if(eatCount == sharkSize){
            eatCount = 0;
            sharkSize++;
        }

        boolean[][] visited = new boolean[N][N];

        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(sharkRow, sharkCol, 0));
        visited[sharkRow][sharkCol] = true;

        int minRow = Integer.MAX_VALUE;
        int minCol = Integer.MAX_VALUE;
        int minTime = Integer.MAX_VALUE;

        while(!q.isEmpty()){
            Node a = q.poll();
            //최소 시간으로 물고기를 먹을 수 있는 시간을 넘으면 종료
            if(a.time >= minTime)
                break;

            for(int i = 0; i<4; i++){
                int dr = a.row + dR[i];
                int dc = a.col + dC[i];

                if(dr<0||dc<0||dr>=N||dc>=N)
                    continue;
                if(visited[dr][dc])
                    continue;
                if(map[dr][dc] > sharkSize)
                    continue;

                //아기 상어가 먹을 수 있는 물고기가 있는 칸에 들어옴
                if(map[dr][dc]>0 && map[dr][dc]<sharkSize){
                    if(dr<minRow){
                        minRow = dr;
                        minCol = dc;
                        minTime = a.time + 1;
                    }
                    else if(dr == minRow){
                        if(dc < minCol){
                            minCol = dc;
                            minTime = a.time + 1;
                        }
                    }
                }

                q.offer(new Node(dr, dc, a.time+1));
                visited[dr][dc] = true;
            }
        }

        if(minTime == Integer.MAX_VALUE)
            return false;
        else {
            sharkRow = minRow;
            sharkCol = minCol;
            eatCount++;
            time = minTime;
            map[sharkRow][sharkCol] = 0;

            return true;
        }
    }
}
class Node{
    int row, col, time;

    Node(int row, int col, int time){
        this.row = row;
        this.col = col;
        this.time = time;
    }
}

아기 상어가 물고기를 먹으러 이동할 수 있다면 minTime이 Integer.MAX_VALUE가 아니라서 true를 반환합니다.

그리고 아기 상어가 물고기를 먹기 위해서 엄마 상어의 도움이 필요하다면 반복문을 종료하게 하였습니다.