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

16236번: 아기 상어

 

풀이 과정

이 문제는 BFS를 구현하면 되는 문제지만 조건이 매우 복잡하다

이동 조건은 다음과 같다

 

• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 감
• 먹을 수 있는 물고기가 1마리보다 많다면, 다음 우선 순위로 먹으러 감
  • 거리가 가까운 순서
  • 위, 왼쪽으로 가까운 순서
• 더 이상 먹을 수 있는 물고기가 공간에 없다면 종료
• 상어의 이동은 1초가 걸림
• 상어는 자신의 크기만큼 물고기를 먹으면 크기가 1 커짐

 

위 조건들을 맞추면서 BFS 탐색을 해야한다

하나씩 구현해나가보자

 

1. 좌표를 담을 class 생성

class Spot {

  int x;
  int y;
  int move;

  public Spot(int x, int y, int move) {
    this.x = x;
    this.y = y;
    this.move = move;
  }
}

가독성을 위해 좌표를 담을 Spot 클래스를 만든다 

x와 y좌표, 이동거리를 담은 move 변수가 있다

 

2. BFS를 위한 우선순위 큐

PriorityQueue<Spot> queue = new PriorityQueue<>(
        (spot1, spot2) -> spot1.move != spot2.move ? Integer.compare(
            spot1.move, spot2.move)
            : (spot1.x != spot2.x ? Integer.compare(spot1.x, spot2.x) : Integer.compare(spot1.y,
                spot2.y)));

• 먹을 수 있는 물고기가 1마리보다 많다면, 다음 우선 순위로 먹으러 감
  • 거리가 가까운 순서
  • 위, 왼쪽으로 가까운 순서

Spot이 여러개가 들어왔을 때 위 조건을 만족시키기 위해서 우선순위를 가진 큐를 이용한다

1. 거리가 가까운 순서
2. x 좌표가 작은 순서
3. y 좌표가 작은 순서

위 순서대로 우선순위를 갖는 Queue다

나머지는 결과코드 안에 주석으로 적었다

 

결과 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

  private static int N;

  private static int size; // 상어의 현재 크기
  private static int count; // 상어가 먹이를 먹은 수
  private static int answer; // 상어의 총 이동 횟수
  private static Spot location; // 상어의 현재 위치
  private static int[][] moveXY = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};// 상어의 이동

  private static int[][] space; // 상어와 물고기 위치 저장소

  public static void main(String[] args) throws IOException {
    Main.start();
  }

  private static void start() throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;

    // 입력
    N = Integer.parseInt(br.readLine());
    space = new int[N][N];
    size = 2;
    count = 0;
    answer = 0;
    location = new Spot(0, 0, 0);

    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < N; j++) {
        space[i][j] = Integer.parseInt(st.nextToken());
        if (space[i][j] == 9) {
          location.x = i;
          location.y = j;
        }
      }
    }

    // 계산
    while (true) {
      Spot result = bfs(location.x, location.y);

      // bfs 탐색을 했는데 move가 -1 일 경우 (= 먹을 물고기가 없을 경우) break
      if (result.move <= 0) {
        break;
      }

      answer += result.move; // 이동 횟수 추가
      location = result; // 상어 위치 최신화
    }

    // 결과 출력
    System.out.println(answer);
  }


  // 가장 가까운 물고기 bfs 로 찾기
  // @return 가장 가까운 물고기 위치와 이동 횟수, 찾는 물고기 없으면 {-1, -1, -1} return
  private static Spot bfs(int x, int y) {
    
    // 조건에 맞는 우선순위 큐
    PriorityQueue<Spot> queue = new PriorityQueue<>(
        (spot1, spot2) -> spot1.move != spot2.move ? Integer.compare(
            spot1.move, spot2.move)
            : (spot1.x != spot2.x ? Integer.compare(spot1.x, spot2.x) : Integer.compare(spot1.y,
                spot2.y)));

    boolean[][] visit = new boolean[N][N];

    space[x][y] = 0;
    visit[x][y] = true;

    queue.add(new Spot(x, y, 0));

    while (!queue.isEmpty()) {
      Spot oldSpot = queue.poll();
      int oldX = oldSpot.x;
      int oldY = oldSpot.y;

      // 먹을 수 있다면
      if (canEat(oldSpot)) {
        // 상어 size 만큼 물고기를 먹었다면
        if (++count == size) {
          count = 0;
          size++;
        }
        space[oldX][oldY] = 0; // 물고기 제거
        return oldSpot;
      }

      for (int i = 0; i < 4; i++) {
        Spot newSpot = new Spot(oldX + moveXY[i][0], oldY + moveXY[i][1], oldSpot.move + 1);

        int newX = newSpot.x;
        int newY = newSpot.y;

        // 범위 체크
        if (!isInBoundary(newSpot)) {
          continue;
        }

        // 방문 체크
        if (visit[newX][newY]) {
          continue;
        }

        visit[newX][newY] = true;

        // 이동 가능한지 체크
        if (!canMove(newSpot)) {
          continue;
        }

        queue.offer(newSpot);
      }
    }

    // 먹을 수 있는 물고기가 없다면 -1 출력
    return new Spot(-1, -1, -1);
  }

  // 상어가 물고기를 먹을 수 있는 크기 체크
  private static boolean canEat(Spot spot) {
    if (space[spot.x][spot.y] >= size || space[spot.x][spot.y] == 0) {
      return false;
    }
    return true;
  }

  // 상어가 이동할 수 있는 칸 체크
  private static boolean canMove(Spot spot) {
    if (space[spot.x][spot.y] > size) {
      return false;
    }
    return true;
  }

  // 탐색 범위 유효성 체크
  private static boolean isInBoundary(Spot spot) {
    if (spot.x < 0 || spot.y < 0 || spot.x >= N || spot.y >= N) {
      return false;
    }
    return true;
  }
}


class Spot {

  int x;
  int y;
  int move;

  public Spot(int x, int y, int move) {
    this.x = x;
    this.y = y;
    this.move = move;
  }
}