[백준]JAVA - 16236번: 아기 상어

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

16236번: 아기 상어

풀이

조건이 많아서 생각할 게 많았던 bfs 문제로 알고리즘 진행 과정을 보면서 설명하겠다.

 

1. 입력받은 값 중에 '9'는 아기 상어의 위치이며 아기 상어는 총 1마리만 존재한다.

  1) 아기 상어의 x, y 좌표를 저장함 (shark_x, shark_y) 

  2) 저장 후에 아기 상어의 위치는 0으로 변경한다. (해당 위치도 탐색 과정에 포함되어야함)

  3) 물고기 위치를 담을 수 있는 배열 (fish) 과 bfs 탐색을 위한 Queue 를 생성한다.

  4) 아기 상어의 초기 사이즈는 2이다.

 

2. while 문 안에서 bfs 탐색을 시작한다.

  1) 1번에서 저장해두었던 아기 상어 위치를 q에 넣어준 후에 4방향으로 가면서 현재 크기에서 잡아먹을 수 있는 물고기의 위치를 찾는다.

  2) 아기 상어의 크기보다 작은 물고기만 먹을 수 있다. → fish 배열에 담는다.

  3) 아기 상어와 물고기 크기가 같으면 지나갈 수 있다. (먹을 수는 없음) → Queue 에 넣어서 bfs 탐색을 진행한다.

 

3. bfs 탐색이 끝났으면 물고기를 잡아먹는다. hunt()

  1) fish 배열에 담긴 물고기 중에서 현재 아기 상어의 위치와 가장 가까운 걸 잡아먹는다.

  2) 거리가 같다면 x축이 제일 작은 위치의 물고기를 잡아먹는다. (제일 위쪽)

  3) x축도 같다면 y축이 제일 작은 위치의 물고기를 잡아먹는다. (제일 왼쪽)

  4) 물고기를 잡아먹은 후에 아기 상어 위치를 해당 물고기의 위치로 변경한다.

       shark_x = hunting.x,

       shark_y = hunting.y

  5) 상어 크기만큼 물고기를 먹었다면 상어 크기를 1 증가시킨 후에 먹은 횟수는 초기화한다.

       shark_size++

  

4. 더 이상 먹을 수 있는 물고기가 없을 때까지 2, 3번을 반복한다.

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int N;
    static int shark_x, shark_y, shark_size;
    static int[][] map;
    static ArrayList<Position> fish;

    static int result = 0;
    static int hunt_cnt = 0;
	
    public static class Position {
        int x;
        int y;
        int t;
		
        public Position (int x, int y, int t) {
            this.x = x;
            this.y = y;
            this.t = t;
        }
    }
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];      // 지도
        fish = new ArrayList<>(); // 현재 잡을 수 있는 물고리 위치를 담는 배열
        shark_size = 2;           // 상어 초기 크기
		
        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;
                    map[i][j] = 0;
                }
            }
        }
		
        // 잡을 수 있는 물고기가 없을 때 까지 반복
        while (true) {
            // 현재 크기에서 먹을 수 있는 물고기 위치 찾기
            bfs(shark_x, shark_y);
			
            // 뽑아온 물고기 위치 중에서 제일 위에서 왼쪽 물고기부터 잡아먹고 상어 위치 조정
            if (hunt()) {
                System.out.println(result);
                break;
            }	
        }
    }
	
    public static void bfs(int x, int y) {
        Queue<Position> q = new LinkedList<>();  // 상어 위치
        boolean[][] visited = new boolean[N][N]; // 방문 처리
        q.add(new Position(x, y, 0));
        visited[x][y] = true;
		
        while (!q.isEmpty()) {
            Position now = q.poll();
			
            for (int i=0; i<4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                int nt = now.t + 1;
				
                // 범위를 벗어나거나 방문한 경우 
                if (nx < 0 || nx > N-1 || ny < 0 || ny > N-1 || visited[nx][ny]) continue;
				
                // 이동 가능한 경우
                if (map[nx][ny] == 0 || map[nx][ny] <= shark_size) {
                    q.add(new Position(nx, ny, nt));
                    visited[nx][ny] = true;
                }
				
                // 먹을 수 있는 경우 물고기 배열에 담음
                if (0 < map[nx][ny] && map[nx][ny] < shark_size) {
                    fish.add(new Position(nx, ny, nt));
                    visited[nx][ny] = true;
                }
            }
        }
    }
	
    public static boolean hunt() {
        // 현재 크기에서 잡을 수 있는 물고기 리스트에서 제일 위, 왼쪽에 있는 물고기를 뽑음
        if (fish.size() > 0) {
            Position hunting = fish.get(0);
            for (int i=1; i<fish.size(); i++) {
				
                if (hunting.t > fish.get(i).t) {
                    hunting = fish.get(i);
                }
				
                // 거리가 같은 경우
                else if (hunting.t == fish.get(i).t) {
					
                    // 맨 위부터 먹는다.
                    if (hunting.x > fish.get(i).x) {
                        hunting = fish.get(i);
					
                    // 거리가 같고 x축도 같을 경우 맨 왼쪽부터 먹는다.
                    } else if (hunting.x == fish.get(i).x) {
                        if (hunting.y > fish.get(i).y) {
                            hunting = fish.get(i);
                        }
                    }
                }
            }
							
            result += hunting.t;           // 상어가 이동한 거리 증가
            hunt_cnt++;                    // 먹은 횟수
            map[hunting.x][hunting.y] = 0; // 물고기를 먹었으므로 0으로 초기화
            fish.clear();                  // 물고기를 담은 배열 초기화
			
            // 상어 위치 초기화
            shark_x = hunting.x;
            shark_y = hunting.y;
			
            // 상어 크기만큼 물고리를 먹었다면 크기 증가
            if (hunt_cnt == shark_size) {
                shark_size++;
                hunt_cnt = 0;
            }
        } else {
            return true; // 먹을 수 있는 물고기가 없을 경우
        }
		
        return false;
    }
}