[백준 16236] 아기 상어

 

 

아기 상어가 도움을 요청하지 않고 사냥도 안하고 무한정 머무를 수 있으므로 문제에서 요구하는 것은

최소 시간이다. 따라서 BFS로 배열을 순회하면 되겠다.

 

탐색 조건이 까다로워 BFS 를 "잘" 구현해야한다.

 

*조건

1. 물고기 크기가 상어보다 작아야 잡아먹을 수 있다.

2. 물고기 크기와 상어의 크기가 같다면 크 위치로 이동할 수 있지만 먹을수는 없다.

3. 잡아먹을 수 있는 물고기가 여러마리이면 가장 위쪽의 물고기를 먹는다.

3-1. 3번 조건에서 가장 위쪽에 물고기가 없다면 가장 왼쪽의 물고기를 먹는다.

4. 잡아먹을 수 있는 물고기가 없다면 엄마 상어를 부른다.

 

 

필자가 구현할 로직을 아래에 서술하겠다.

 

1. 아기 상어의 위치에서 BFS 를 한다.

2. 잡아먹을수 있는 물고기가 있으면 잡아먹고 BFS를 멈춘다.

2-1. 잡아먹을 수 있는 물고기가 여러마리 였다면 우선순위대로 처리하고 잡아먹은 위치에서 다시 BFS를 한다.

3. 잡아먹을 수 있는 물고기가 없고 이동할 수 있다면 BFS를 계속한다.

4. 배열내에 잡아먹을 수 있는 물고기가 없다면 정지한다.

 

 

주석을 상세히 달아놓았다.

 

public class Main {

	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int a[][] = new int[n][n];
        
        int x = 0, y = 0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                a[i][j] = sc.nextInt();
                if(a[i][j] == 9) {
                    x = i;
                    y = j;
                }
            }
        }
        //처음 위치 저장
        
        int dx[] = {-1, 0, 1, 0};
        int dy[] = {0, -1, 0, 1};
        int size = 2; //아기 상어의 처음 크기
        int eat = 0; //물고기 잡아먹은 횟수
        int time = 0; //총 사냥 시간
        while(true) {
            Queue<Shark> q = new LinkedList<Shark>(); //BFS 할 큐
            ArrayList<Shark> fish = new ArrayList<Shark>(); //잡아먹을 물고기를 보관할 리스트
            boolean visited[][] = new boolean[n][n]; //방문 기록(반복문을 중지하기 위해 필요)
            
            q.offer(new Shark(x, y, 0));
            visited[x][y] = true;
            
            int find = -1; //물고기를 하나도 발견하지 못했다면 정지시키는 변수
            while(!q.isEmpty()) {
                Shark shark = q.poll();
                int sx = shark.x;
                int sy = shark.y;
                int move = shark.move;
                
                if(find == move) break; //아래 로직에서 물고기를 먹었다면 BFS를 종료시킨다
                
                for(int i=0; i<4; i++) {
                    int nx = sx + dx[i];
                    int ny = sy + dy[i];
                    if(0 <= nx && nx < n && 0 <= ny && ny < n) {
                        if(a[nx][ny] <= size && !visited[nx][ny]) {
                            if(0 < a[nx][ny] && a[nx][ny] < size) {
                                find = move + 1; //먹었다면 find 변수에 이동거리를 대입
                                fish.add(new Shark(nx, ny, move + 1)); //먹은 물고기 리스트에 추가
                            }
                            q.offer(new Shark(nx, ny, move + 1)); //BFS 큐에 추가
                            visited[nx][ny] = true;
                        }
                    }
                }
            }
            
            if(find == -1) break; //먹을 물고기가 없다면 로직을 종료시킨다
            else {
                Shark f = fish.get(0);
                for(int i=1; i<fish.size(); i++) {
                    if(f.x > fish.get(i).x) {
                        f = fish.get(i);
                        continue;
                    } else if(f.x == fish.get(i).x) {
                        if(f.y > fish.get(i).y) {
                            f = fish.get(i);
                        }
                    }
                }
                //잡아먹은 물고기가 여러마리라면 위 -> 왼쪽 물고기를 우선으로 먹게함

                time += find; //경과시간 변수에 이동거리를 더해준다
                a[x][y] = 0; //처음 아기상어의 위치 초기화
                a[f.x][f.y] = 9; //다시 BFS할 시작 위치를 물고기를 잡아먹은 위치로 지정함
                x = f.x;
                y = f.y;
                if(size == ++eat) {
                    size++;
                    eat = 0;
                }
                //상어의 크기가 잡아먹은 횟수와 같다면 크기를 키운다
            }
        }
        System.out.println(time);
    }
    
    static class Shark {
        int x;
        int y;
        int move;
        
        Shark(int x, int y, int move) {
            this.x = x;
            this.y = y;
            this.move = move;
        }
    }
}