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

문제 링크

16236번: 아기 상어

 

풀이 ) BFS

  현재 아기상어 위치를 시작으로 BFS로 먹이 후보를 찾고

  후보 중 조건에 만족하는 먹이로 이동하기를 이동할 수 없을 때까지 반복한다.

 

코드 )

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

class Main {

    static int n;
    static int[][] board;
    static boolean[][] visited;
    static Fish shark;
    static Fish next;
    static Queue<Fish> q;

    static int answer;

    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};

    public static void main(String[] args) throws IOException {
        input();	// 입력
        solve();	// 풀이
    }

    static void solve() {

        while(true) {
            int distance = init();	// 현재 상어 위치부터 다음 먹이까지의 거리 (초기화)

            while(!q.isEmpty() && next == null) {	// 다음 물고기가 없을때까지
                int size = q.size();
                distance++;
                while (size-- > 0) {
                    Fish cur = q.poll();
                    /*
                     * 다음 물고기의 크기가 더 작은 지 확인하고
                     * 더 작으면 먹을 수 있는 다른 물고기와 위치를 비교하여 갱신
                     */
                    promise(cur.x, cur.y);

                    for (int dir = 0; dir < 4; ++dir) {
                    	// 다음 위치로 이동할 수 있으면 추가
                        findRoute(cur.x+dx[dir], cur.y+dy[dir]);
                    }
                }
            }

            if(next != null) {
            	// 이동 가능한 경우
                move(distance);
            } else {
            	// 이동 불가능한 경우
                System.out.println(answer);
                break;
            }
        }
    }

    static void move(int distance) {
        answer += distance;
        // 물고기를 먹고
        board[next.x][next.y] = 0;
        shark = next;
        // 크기가 증가할 수 있으면 증가
        shark.grow();
    }

    static void findRoute(int x, int y) {
        if (!isIn(x, y) || visited[x][y] || board[x][y] > shark.size){
            return;
        }

        visited[x][y] = true;
        q.offer(new Fish(x, y, board[x][y], -1));
    }

    static void promise(int x, int y) {
        if (board[x][y] > 0 && board[x][y] < shark.size) {
            Fish candidate = new Fish(x, y, shark.size, shark.feed+1);
            if(next == null ||
                    candidate.x < next.x ||
                    (candidate.x == next.x && candidate.y < next.y)) {
                next = candidate;
            }
        }
    }

    static int init() {
        visited = new boolean[n][n];
        q = new LinkedList<>();
        q.offer(shark);
        visited[shark.x][shark.y] = true;
        next = null;
        return -1;
    }

    static boolean isIn(int nx, int ny) {
        return nx>=0&&nx<n&&ny>=0&&ny<n;
    }

    static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new int[n][n];
        for(int i = 0; i < n; ++i) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < n; ++j) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if(board[i][j] == 9) {
                    shark = new Fish(i, j, 2, 0);
                    board[i][j] = 0;
                }
            }
        }
    }

    static class Fish {
        int x, y;
        int size;
        int feed;

        public Fish(int x, int y, int size, int feed) {
            this.x = x;
            this.y = y;
            this.size = size;
            this.feed = feed;
        }

        void grow() {
            if(feed == size) {
                size++;
                feed = 0;
            }
        }
    }
}

 

주의 )

  단순히 상, 좌, 우, 하 순으로 검사하게되면 4번 예시 케이스에서 답인 60이 아닌 56이 출력된다.