[JAVA/BFS] 백준 16236 아기 상어

1. 문제

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

16236번: 아기 상어

 

2. 풀이

BFS를 통해 상어의 위치를 이동해가며, 먹을 수 있는 물고기 중 가장 작은 거리를 선택하고 더이상 먹을 수 없는 물고기가 없을 때까지 이 과정을 반복해 답을 구한다. 전체적인 풀이 과정은 아래와 같다.

1. 상어의 위치를 저장하고, 상어의 위치에서부터 탐색을 시작한다.
   • 상어의 위치에서 BFS를 해 상어의 위치를 이동시킨다. 상어가 갈 수 있는 경우는 (1) 상어의 크기보다 작아 물고기를 먹을 수 있는 경우 (2) 빈공간이거나 상어 크기와 같아 물고기를 지날 수 있는 경우로 2가지다. 이 중, 먹을 수 있는 경우 물고기의 좌표와 그때의 시간(거리)를 저장(fishList)한다.
2. 더이상 먹을 수 있는 물고기가 없으면(fishList.isEmpty() == true) 이때까지의 시간을 출력한 후 종료한다.
3. 더이상 먹을 수 있는 물고기가 있으면 물고기의 목록을 우선순위에 맞게 정렬한다. 정렬하면 가장 앞에 있는 물고기가 우선순위가 가장 높으므로 해당 물고기를 먹을 물고기(fishToEat)로 정한다.
   • 거리 오름차순 -> x 좌표 오름차순 -> y좌표 오름차순으로 정렬한다. Comparator를 사용해 정렬한다.
4. 해당 물고기를 먹는데까지 걸린 시간을 전체 걸린 시간(time)에 추가한다. 먹은 물고기의 갯수를 증가시키고 map에서 0으로 처리해 물고기를 먹었음을 표시한다. 현재 상어의 위치를 갱신한다.
   • 상어의 크기와 현재까지 먹은 물고기 갯수가 같으면 상어가 커질 수 있는 조건이므로 상어의 크기를 증가시킨다.
5. 더이상 먹을 물고기가 없을때까지 1~4의 과정을 반복한다.

 

3. 코드

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

class Main{
    
    static int n;
    static int[][] map;
    static Fish shark;
    
    // 먹이가 될 물고기
    private static class Fish{
        int x, y, dist;
        
        public Fish(int x, int y, int dist){
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
    }
    
    // bfs
    private static void solve(){
        Queue<Fish> q = new LinkedList<>();
        boolean[][] visited = new boolean[n][n]; // 방문여부 체크
        int time = 0; // 물고기를 잡아먹을 수 있는 시간
        ArrayList<Fish> fishList = new ArrayList<Fish>(); // 먹을 수 있는 물고기
        
        int nowSize = 2; // 상어 크기
        int fishCnt = 0; // 먹은 물고기 갯수
        
        int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};
        while(true){
            
            visited = new boolean[n][n];
            
            visited[shark.x][shark.y] = true;
            q.add(shark);
            
            while(!q.isEmpty()){
                Fish now = q.poll();
                
                for(int i = 0; i < 4; i++){
                    int nX = now.x + dir[i][0];
                    int nY = now.y + dir[i][1];
                    
                    if(nX < 0 || nY < 0 || nX >= n || nY >= n) continue;
                    if(visited[nX][nY]) continue;
                    
                    if(map[nX][nY] != 0 && map[nX][nY] < nowSize){ // 먹을 수 있는 경우
                        fishList.add(new Fish(nX, nY, now.dist+1));
                        q.add(new Fish(nX, nY, now.dist+1));
                        visited[nX][nY] = true;
                    }else if(map[nX][nY] == 0 || map[nX][nY] == nowSize){ // 지날 수 있는 경우
                        q.add(new Fish(nX, nY, now.dist+1));
                        visited[nX][nY] = true;
                    }
                }
            }
            
            if(fishList.isEmpty()){ // 더이상 먹을 물고기가 없는 경우
                System.out.println(time);
                return;
            }else{
                
                // 거리 -> x좌표 -> y좌표 오름차순 정렬
                Collections.sort(fishList, new Comparator<Fish>(){
                    @Override
                    public int compare(Fish f1, Fish f2){
                        if(f1.dist == f2.dist) {
                            if(f1.x == f2.x){
                                return Integer.compare(f1.y, f2.y);
                            }else{
                                return Integer.compare(f1.x, f2.x);
                            }
                        }else{
                            return Integer.compare(f1.dist, f2.dist);
                        }
                    }
                });
            }    
            
            Fish fishToEat = fishList.get(0); // 먹을 물고기
            time += fishToEat.dist; // 먹은 물고기의 거리를 time에 추가
            fishCnt++; // 먹은 물고기의 갯수 카운트
            map[fishToEat.x][fishToEat.y] = 0; // 물고기 먹음 처리
                
            if(nowSize == fishCnt){
                nowSize++;
                fishCnt = 0;
            }
            
            shark.x = fishToEat.x;
            shark.y = fishToEat.y;
            fishList.clear();
        }
        
    }
    
    public static void main (String[] args) throws java.lang.Exception{
        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++){
            String[] input = br.readLine().split(" ");
            for(int j = 0; j < n; j++){
                map[i][j] = Integer.parseInt(input[j]);
                
                if(map[i][j] == 9){ // 아기상어 위치
                    shark = new Fish(i, j, 0);
                    map[i][j] = 0;
                }
            }
        }
        
        solve();
    }
}​