우매함의 봉우리를 넘어서며 개발하면서 기록하기

백준 16236. 아기 상어


문제 바로가기

아기 상어


문제 요약

N * N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 존재한다고 한다. 아기상어는 문제에서 제시된 조건에 맞게 이동을 결정하고, 본인보다 크기가 큰 물고기가 있는 칸은 들어가지 못하며 같은 크기를 갖고 있는 물고기가 있으면 지나갈 수만 있다고 한다.

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

이때 아기 상어가 물고기를 얼마나 잡아먹을 수 있는지 찾는 프로그램을 작성하는 문제이다.


문제 풀이 포인트


  1. 처음 초기화 때 상어의 위치를 찾아 전역 변수에 저장하여 활용.

  2. 제일 가까운 물고기의 거리를 찾기 위해 BFS 사용!!
    • BFS를 사용할 때 상어가 한칸 움직일 때마다 이동한 시간을 1씩 늘려야 하므로 Point 객체에 time 값을 같이 넣어서 전달.
    • 물고기를 잡아먹은 횟수를 카운트하기 위해 cnt 변수도 추가.
  3. BFS 탐지 중에 잡아먹을 수 있는 물고기가 나오면 그 거리를 최소 거리로 정하고 위치를 List에 저장.
    • 아직 queue에 들어있는 위치 중 같은 최소 거리 안에 먹을 수 있는 물고기가 있는지 모두 조사.
    • 만약 최소 거리에 먹을 수 있는 물고기가 여러마리 있다면 조건에 따라 한마리를 결정.
    • 풀이에서는 Point 객체의 Comparable을 이용하여 리스트를 정렬하고 첫번째 객체를 불러오는 것으로 가장 최단 거리의 물고기를 결정하였음.

문제 코드[JAVA]

코드 펼치기


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
  static int[][] map;
  static int n, size = 2; // 상어의 크기
  static Point shark = new Point(0, 0, 0, 0);

  static class Point implements Comparable<Point> {
    int x, y, cnt, time;

    public Point(int x, int y, int cnt, int time) {
      super();
      this.x = x;
      this.y = y;
      this.cnt = cnt;
      this.time = time;
    }

    @Override
    public int compareTo(Point o) {
      int diff = this.x - o.x;
      return diff != 0 ? diff : this.y - o.y;
    }
  }
  static int[] dx = { -1, 0, 1, 0 };
  static int[] dy = { 0, -1, 0, 1 };

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    map = new int[n][n];
    for (int i = 0; i < n; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < n; j++) {
        map[i][j] = Integer.parseInt(st.nextToken());
        if (map[i][j] == 9) {
          shark.x = i;
          shark.y = j;
        }
      }
    }
    find_bfs();
    System.out.println(shark.time);
  }

  private static void find_bfs() {
    // 상어의 위치에서 가까운 물고기 찾기

    while (true) {
      Queue<Point> queue = new LinkedList<>();

      queue.add(shark);
      map[shark.x][shark.y] = 0;
      boolean[][] visited = new boolean[n][n];
      ArrayList<Point> fish_list = new ArrayList<>();

      visited[shark.x][shark.y] = true;
      int distance = -1;
      while (!queue.isEmpty()) {
        Point p = queue.poll();
        if (p.time == distance) break;
        for (int d = 0; d < 4; d++) {
          int nx = p.x + dx[d];
          int ny = p.y + dy[d];
          if (safy(nx, ny) && !visited[nx][ny]) {
            visited[nx][ny] = true;        
            if (map[nx][ny] == 0) {
              queue.add(new Point(nx, ny, p.cnt, p.time + 1));
            } else {
              if (map[nx][ny] > size) {
                continue;
              } else if (map[nx][ny] < size) {
                distance = p.time + 1;
                fish_list.add(new Point(nx, ny, p.cnt+1, p.time+1));							
              } else {              
                queue.add(new Point(nx, ny, p.cnt, p.time + 1));
              }
            }
          }
        }
      }
      if (distance == -1) { // 거리 내에 물고기가 없음
        break;
      } else {
        if (!fish_list.isEmpty()) {
          Collections.sort(fish_list);
        }
      }
      shark = fish_list.get(0);
      if (shark.cnt == size) {
        size++;
        shark.cnt = 0;
      }
    }
  }

  private static void print() {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        System.out.print(map[i][j] + " ");
      }
      System.out.println();
    }
  }

  private static boolean safy(int x, int y) {
    if (x >= 0 && x < n && y >= 0 && y < n) {
      return true;
    } else {
      return false;
    }
  }
}