[BOJ 16236] 아기상어 - JAVA

백준 아기상어 문제를 설명해보려고 한다. bfs, dfs 그래프 알고리즘만 사용해서 문제를 풀다가 처음으로 (?) 구현까지 포함되어 있는 문제를 풀려고 하니 너무 빡셌다,,, 그래서 우선순위 큐도 생각했다가,,, 난리를 치다가 안될 거 같아서 구글의 힘을 빌렸다.

 

https://velog.io/@skyepodium/%EB%B0%B1%EC%A4%80-16236-%EC%95%84%EA%B8%B0-%EC%83%81%EC%96%B4

백준 16236 아기 상어

 

우선, 문제부터 보도록 하자

 

문제부터 매우 길다,, 문제가 많다!!

 

문제 설명

1. 아기상어의 초기값 = 2, 자기의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1씩 증가, 물고기의 수는 먹을 때 마다 초기화

2. 자기의 크기보다 작은 물고기는 먹을 수 있고, 자기와 크기가 같은 물고기는 먹지는 못하고 지나 갈 수 있다, 자기보다 큰 물고기는 지나가거나 먹을 수 없다.

3. 상어는 한 번에 한 칸씩 움직일 수 있다.

4.  상어는 거리가 가까운 물고기부터 먹는다, 만약 같은 거리에 먹을 수 있는 물고기가 많다면 가장 위에 있는 물고기 먼저 먹어야하고 가장 위에 있는 물고기가 여러마리라면 가장 왼쪽에 있는 물고기를 먹어야한다.

 

생각할 것이 매우많다.

 

구현방법

새로운 노드를 방문할 때마다 거리를 계산해서 저장한다. 거리를 비교하여 최소 거리를 계산한다.(가장 중요)

 

자세한 설명은 코드 주석을 통해 설명을 하도록 하겠다.

 

 

import java.util.*;
import java.io.*;
class Node{
    int x,y;
    Node(int x, int y){
        this.x = x;
        this.y = y;
    }
    int getX() {
        return x;
    }
    int getY() {
        return y;
    }
}
public class Main{
  static int n;    //공간 크기
  static int shark_size = 2;    //상어 크기 초기화
  static int fish;    //물고기 먹는 개수
  static int[][] graph;    //공간좌표
  static int[][] visited;    //방문한 곳 좌표
  static int[] dx = {-1,0,1,0};    //x이동값
  static int[] dy = {0,-1,0,1};    //y이동값
  static int min_x, min_y;    //최소거리 좌표
  static int min_dist;    //최소거리
  
  static void bfs(int x, int y) {
      Queue<Node> q = new LinkedList<>();
      q.offer(new Node(x, y));
      while(!q.isEmpty()) {
          int k = q.size();
          for(int i = 0;i<k;i++) {
              Node node = q.poll();
              x = node.x;
              y = node.y;
              for(int j = 0;j<4;j++) {
                  int nx = x+dx[j];
                  int ny = y+dy[j];
                  
                  if(nx>=n||ny>=n||nx<0||ny<0)
                      continue;
                  if(visited[nx][ny]>0||graph[nx][ny]>shark_size)
                      //방문 했거나, 상어보다 큰 물고기는 지나가지 못한다.
                      continue;
                  
                  if(graph[nx][ny]==0||graph[nx][ny]==shark_size)
                      //방문한 곳에 물고기가 없거나 상어랑 크기가 같다면 지나간다
                      visited[nx][ny]=visited[x][y]+1;
                  
                  /*상어 크기보다 작은 물고기 위를 지나가게 된다면 최소거리와
                   * 현재 노드의 방문 수를 비교하여
                   * 최소 거리보다 작으면 최소거리와 현재 방문 수를 바꾼다
                   * 중요!! 최소 거리와 현재 방문 수가 같다면
                   * x값이 작은 것이 최소 좌표가 된다
                   * 즉, 좌표 상에서 더 높은 곳에 위치하는 좌표가 최소좌표가 된다.
                   * 만약, x값도 같다면 y값이 작은 것이 최소 좌표가 된다. 
                       즉, 좌표 상에서 더 왼쪽에 위치하는 좌표가 최소 좌표가 된다.*/
                  else if(graph[nx][ny]<shark_size) {
                      visited[nx][ny]=visited[x][y]+1;
                      if(min_dist>visited[nx][ny]) {
                          min_dist = visited[nx][ny];
                          min_x = nx;
                          min_y = ny;
                      }
                      else if(min_dist == visited[nx][ny]) {
                          if(min_x > nx) {
                              min_x = nx;
                              min_y = ny;
                          }
                          else if(min_x == nx) {
                              if(min_y>ny) {
                                  min_x = nx;
                                  min_y = ny;
                              }
                          }
                      }
                  }
                  q.offer(new Node(nx, ny));
              }
          }
      }
  }
   public static void main(String args[]) throws Exception{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      
      n = Integer.parseInt(br.readLine());
      StringTokenizer stok;
      graph = new int[n][n];
      visited = new int[n][n];
      
      int shark_x = 0, shark_y = 0;    //상어 위치좌표
      int cnt = 0;    //최종 이동거리
      
      for(int i=0;i<n;i++) {
          stok = new StringTokenizer(br.readLine());
          for(int j=0;j<n;j++) {
              graph[i][j] = Integer.parseInt(stok.nextToken());
              if(graph[i][j]==9) {
                  shark_x = i;
                  shark_y = j;
                  graph[i][j] = 0;
              }
          }
      }
      
      while(true) {
          /*시작할 때와 물고기 한 번 먹을 때 마다
               최소 거리, 최소 x좌표,y좌표, 방문배열 초기화하기 */
          min_dist = 400;
          min_x = n;
          min_y = n;
          visited = new int[n][n];
          
          bfs(shark_x,shark_y);
          
          
          /*최소 x좌표와 최소 y좌표가 움직였으면
           * 먹은 물고기 개수를 늘리고 
           * 먹은 물고기 개수와 상어 크기가 같으면 상어 크기를 키우고
               물고기 개수는 초기화, 상어좌표도 먹은 물고기 좌표로 초기화*/
          if(min_x != n||min_y != n) {
              fish++;
              if(fish==shark_size) {
                  shark_size++;
                  fish = 0;
              }
              shark_x = min_x;
              shark_y = min_y;
              cnt += min_dist;
              graph[shark_x][shark_y] = 0;
          }
          else break;
      }
      bw.write(String.valueOf(cnt));
      bw.flush();
   }
}
 
 
 
 

 

 

완성된 코드를 보니까 참고 자료를 보기전에 나는 너무 어렵게 생각했던거 같다... 방문노드에 값을 거리를 계산했음에도 불구하고 이것으로 최소거리를 구한다고는 상상도 못했다,, 다 경험 미숙인듯,,, 더 더 더 많이 연습해야겠다 !!!