[BOJ] 백준 16236 아기상어

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

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

 Input 

4

4 3 2 1

0 0 0 0

0 0 9 0

1 2 3 4

 

 Output 

14

① 처음 상어의 크기 = 2

② 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다.

    (물고기는 상어보다 작기만 하면 되지 크기에 대한 우선순위는 없다.)

    (같은 크기의 물고기는 먹을 수 없지만 해당 지점을 지나갈 수 있다.)

    (상어보다 크기가 큰 물고기가 있는 곳은 지나갈 수 없다.)

③ 상어는 최소 거리에 있는 물고기를 우선적으로 먹는다. (거리 = 지나가는 칸의 개수)

     (상어의 크기만큼 물고기를 먹으면 상어의 크기 + 1 (상어의 성장에 물고기의 크기 X  / 개수 O))

④ (최소거리가 동일한) 물고기가 여러 마리이면 위쪽 →  왼쪽으로 우선순위를 높이 가진다.

 

a. 위와 같이 있을 때, 처음 상단좌측의 ① 을 우선적으로 먹는다. → Total Distance: 2

b. ① 의 위치에서 거리상 ②, ④ 의 거리(=2)는 같기때문에 위쪽에 위치한 (2)로 간다. 

    → Total Distance: 2 + 2 = 4

c. (2)의 위치에서 제일 가까운 (3)의 위치로 간다. → Total Distance: 4 + 2 = 6

d. 마지막 (4)의 위치로 간다.  → Total Distance: 6 + 2 = 8

 

Sample Case 분석

a. 처음 상어의 위치에서 먹을 수 있는 물고기는 [1], [2]로 거리는 동일하지만,

    위치 우선순위상 [1]쪽으로 먼저간다. → Total Distance: 3 

b. 아직 상어의 크기는 2이므로 [2]로 이동한다. 크기 Up(=3) → Total Distance: 3 + 6 = 9

c. 바로 오른쪽 [3]의 위치로 간다. → Total Distance: 9 + 1 = 10 

d. 그 다음 유일한 먹이인 [4]의 위치로 간다.  → Total Distance:  10 + 4 = 14

e. 상어의 크기보다 작은 물고기가 없으므로 종료

 

[다른 Sample Case]

 Input 

6

5 4 3 2 3 4

4 3 2 3 4 5

3 2 9 5 6 6

2 1 2 3 4 5

3 2 1 6 5 4

6 6 6 6 6 6

 

 Output 

60

---

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
  
public class Main {
    static int N;
    static int board[][];
    static int answer = 0;
    static Fish shark;
    static PriorityQueue<Fish> pq;
      
    // for BFS
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static boolean[][] visited;
    static Queue<Vertex> queue;
    static class Fish implements Comparable<Fish>{
        int x, y;
        int size;
        int exp;
        public Fish(int x, int y, int size) {
            this.x = x;
            this.y = y;
            this.size = size;
            exp = 0;
        }
  
        @Override
        public int compareTo(Fish target) {
            // 위쪽에 있는 것이 앞으로 오도록
            if(this.x < target.x) return -1;
            else if(this.x > target.x) return 1;
            else {
                // 동일한 x 좌표일 때, 왼쪽에 있는 것이 앞쪽에 오도록
                if(this.y < target.y) return -1;
                else return 1;
            }
        }
  
        public void eatFish(Fish fish) {
            // 상어 이동
            this.x = fish.x;
            this.y = fish.y;
            board[fish.x][fish.y] = 0;
              
            if(++this.exp == this.size) {
                // 크기 Up
                this.size++;
                // 경험치 초기화
                this.exp = 0;
            }
        }
    }
    static class Vertex {
        int x, y;
        // 상어가 있는 곳에서의 거리
        int distance;
        public Vertex(int x, int y, int distance) {
            this.x = x;
            this.y = y;
            this.distance = distance;
        }
          
    }
       
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
          
        N = Integer.parseInt(sc.next());
        board = new int[N][N];
          
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                board[i][j] = Integer.parseInt(sc.next());
                // 상어인 경우
                if(board[i][j] == 9) {
                    shark = new Fish(i, j, 2);
                    // 상어는 애초에 board에서 표시 X
                    board[i][j] = 0;
                }
            }
        } // end of input data
          
        BFS();
          
        System.out.println(answer);
    }
  
  
    private static void BFS() {
        visited = new boolean[N][N];
        queue = new LinkedList<>();
        pq = new PriorityQueue<>();
        // 가장 가까운 물고기들을 찾는 것이므로 임시 최소거리 설정
        int minDistance = Integer.MAX_VALUE;
          
        // 현재 상어의 위치에서 start
        queue.add(new Vertex(shark.x, shark.y, 0));
          
        while(!queue.isEmpty()) {
            Vertex v = queue.poll();
              
            // 상하좌우 방향
            for(int i=0; i<4; i++) {
                int nx = v.x + dx[i];
                int ny = v.y + dy[i];
                  
                if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                  
                // 방문한 곳인 경우
                if(visited[nx][ny]) continue;
                  
                // 상어보다 큰 물고기의 경우 지나갈 수 없다.
                if(board[nx][ny] > shark.size) continue;
                  
                // 최소거리의 물고기보다 먼 곳은 탐색 불필요
                if(minDistance < v.distance + 1) continue;
                  
                // 상어의 크기 보다 작은 물고기가 발견된다면
                if(board[nx][ny] > 0 && board[nx][ny] < shark.size) {
                    // 최소거리 설정
                    minDistance = v.distance + 1;
                    // 최소거리에 있는 물고기들을 집어넣는다.
                    pq.add(new Fish(nx, ny, board[nx][ny]));
                    // 방문 표시
                    visited[nx][ny] = true;
                    // 이후 탐색은 최소거리 이상이므로 무의미
                    continue;
                }
                  
                // 방문표시
                visited[nx][ny] = true;
                // 최소거리의 물고기를 찾기 위한 BFS 계속 진행
                queue.add(new Vertex(nx, ny, v.distance + 1));
            }
        }
          
        // BFS가 끝난 후, 잡을 수 있는 물고기가 있다면
        if(!pq.isEmpty()) {
            // 가장 우선 순위가 높은 물고기를 먹으로 상어가 이동            
            shark.eatFish(pq.poll());
              
            // 먹을 물고기까지의 BFS를 이용했던 최소 거리를 더해준다.
            answer += minDistance;
              
            // 다음 target을 찾기 위한 재귀
            BFS();
        }
    }
}