[BOJ] 백준 16236 - 아기상어 풀이

1. 문제

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

16236번: 아기 상어

2. 풀이 Point

<Error Point>

• 우선순위에 대하여 정렬하는 방법을 찾지 못함(먹이 큐를 따로 둔다는 것을 생각 못함)….
• BFS를 한 번만 돌고 판단하려함 → 먹이를 먹고 난 후 우선 순위가 달라진다는 것을 생각 못함
• 먹이를 먹고 다시 탐색하려 할 때, 처음 상어가 있었던 위치도 다시 탐색해줘야 하는데, 이를 bfs에서 조건을 걸어주려함 → 상어가 있는 위치는 9인데, 이를 0으로 바꿔주지 않고 bfs에서 9에 대한 조건도 걸어주려함(map[xf][yf] != 9)

<풀이 Point>

• 상어에 대한 객체 정의를 한다.
• 입력값을 받을 때 상어의 위치를 미리 객체로 만들고 시작한다. 이때 상어가 있던 위치를 0으로 만든다.
• 무한 반복을 돌면서 우선 순위 큐를 활용한 bfs 탐색을 실행(먹이 리스트가 나옴) → 먹이를 먹는 함수 실행 → 먹이를 먹고 난 후 먹이 리스트 큐를 초기화 해주고 먹은 위치에서 다시 bfs 탐색을 실행하여 먹이 리스트 갱신
• 먹을 수 있는 먹이가 없다면 무한 반복 탈출
  
  
  

3. 소스 코드

package bfs;

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

public class babyShark {
    static int N;
    static int[][] map;

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

    static int result = 0;  // 이동하는데 걸린 시간

    static class Point {
        int x;
        int y;
        int size; // 상어의 사이즈
        int cnt;  // 먹은 물고기의 개수
        int move; // 이동한 거리

        public Point(int x, int y, int size, int cnt, int move) {
            this.x = x;
            this.y = y;
            this.size = size;
            this.cnt = cnt;
            this.move = move;
        }
    }

    static PriorityQueue<Point> pq; // bfs 한바퀴를 돌았을 때 먹을 수 있는 먹이를 저장한 큐

    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());
        map = new int[N][N];

        Point shark = null;
        for (int i = 0; i < N; i++) {
            StringTokenizer 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 = new Point(i, j, 2, 0, 0);
                    map[i][j] = 0;      // 상어가 있는 자리를 0으로 치환(나중에 탐색할 수 있으므로)
                }
            }
        }

        babySharkSearch(shark);

        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }

    // 먹이를 찾는 bfs
    private static void babySharkSearch(Point shark) {
        // 먹이들의 위치를 저장하는 큐
        pq = new PriorityQueue<>(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                // 거리가 같다면
                if (o1.move == o2.move) {
                    // 거리가 같다면 위쪽에 있는 먹이를 먹어야 하므로 x값을 비교
                    // 그 x값이 같다면 가장 왼쪽에 있는 먹이를 먹어야 하므로 y값이 작은것으로 정렬
                    if (o1.x == o2.x) {
                        return o1.y - o2.y;
                    } else {
                        return o1.x - o2.x;
                    }
                } else {
                    return o1.move - o2.move;
                }
            }
        });

        // bfs를 한번 탐색하면 현재의 상어 위치에서 탐색할 수 있는 먹이들이 pq에 들어간다.
        // 만약 먹이를 먹었다면 그 위치에서부터 다시 나머지 먹이들을 탐색해줘야한다.

        // bfs 탐색에 이용되는 큐
        Queue<Point> q = new LinkedList<>();
        q.add(shark);

        while (true) {
            boolean[][] visited = new boolean[N][N];

            while (!q.isEmpty()) {
                Point poll = q.poll();

                if (!visited[poll.x][poll.x]) {
                    visited[poll.x][poll.y] = true;
                }

                for (int i = 0; i < 4; i++) {
                    int xf = poll.x + dx[i];
                    int yf = poll.y + dy[i];

                    if (xf >= 0 && xf < N && yf >= 0 && yf < N && !visited[xf][yf] && map[xf][yf] <= poll.size) {
                        // 먹이를 먹을 수 있는 경우(현재 상어의 크기가 먹이보다 클 경우) 먹이리스트(pq)에 저장
                        if (map[xf][yf] < poll.size && map[xf][yf] != 0) {
                            pq.add(new Point(xf, yf, poll.size, poll.cnt + 1, poll.move + 1));
                        }

                        visited[xf][yf] = true;
                        q.add(new Point(xf, yf, poll.size, poll.cnt, poll.move + 1));
                    }
                }
            }

            // 더이상 먹을 수 있는 먹이가 없다면
            if (pq.isEmpty()) {
                break;
            }

            // bfs 한바퀴를 돌았다면 (현재 상어의 위치에서 먹을 수 있는 먹이를 우선순위에 맞게 서치했다면) 먹이 함수 실행
            // 먹이 함수가 끝난 후 그 위치부터 다시 탐색해야 하므로 bfs 큐(q)에 넣는다.
            q.add(eat());

            // 다시 탐색해야 하므로 먹이 큐 초기화
            pq.clear();
        } // while(true)
    } // babySharkSearch

    // 먹이를 먹는 함수
    // 하나만 꺼내는 이유 : 먹이를 먹고 다시 우선순위에 따라 탐색해줘야 하기 때문에
    // 그렇다면 bfs를 돌 때 먹이를 찾으면 바로 bfs를 종료시키는 건 안되는가? : 먹이들의 우선순위를 찾아야하기 때문
    private static Point eat() {
        Point poll = pq.poll();

        // 크기가 2인 상어는 2마리의 물고기를 먹어야 크기가 +1 되므로
        if (poll.size == poll.cnt) {
            poll.size++;
            poll.cnt = 0;
        }

        // 이 먹이를 먹을 때까지 이동한 거리 값을 합함
        result += poll.move;

        // 그 위치의 먹이를 먹었으므로 map에서 0으로 만들어줘야함
        map[poll.x][poll.y] = 0;

        return new Point(poll.x, poll.y, poll.size, poll.cnt, 0);
    }
}

• 두 번째로 푼 코드

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

public class Main {
    static int N;
    static int[][] map;
    static class Shark {
        int x;
        int y;
        int weight;
        int cnt;
        int dist;

        public Shark(int x, int y, int weight, int cnt, int dist) {
            this.x = x;
            this.y = y;
            this.weight = weight;
            this.cnt = cnt;
            this.dist = dist;
        }
    }

    static PriorityQueue<Shark> pq;
    static Shark my;

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

    static int result = 0;
    static BufferedReader br;
    static BufferedWriter bw;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());

                if (map[i][j] == 9) {
                    my = new Shark(i, j, 2,0, 0);
                    map[i][j] = 0; // 상어가 출발하고 나면 그 위치를 0으로 바꿔줘야 이동할 수 있음
                }
            }
        }

        // 상어 이동 스타트
        moveBabyShark();

        bw.write(Integer.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }

    private static void moveBabyShark() throws IOException {
        while (true) {
            // 우선순위인 물고기 찾기
            pq = new PriorityQueue<>(new Comparator<Shark>() {
                @Override
                public int compare(Shark o1, Shark o2) {
                    if (o1.dist == o2.dist) {
                        if (o1.x == o2.x) {
                            return o1.y - o2.y;
                        }
                        return o1.x - o2.x;
                    }
                    return o1.dist - o2.dist;
                }
            });

            visited = new boolean[N][N];
            searchFishBFS();

            // 먹을 수 있는 물고기가 없음
            if (pq.isEmpty()) {
                break;
            } else {
                my = eatFish();
            }
        }
    }

    // 물고기 찾기 BFS
    private static void searchFishBFS() {
        Queue<Shark> q = new ArrayDeque<>();
        q.add(my);
        visited[my.x][my.y] = true;

        while (!q.isEmpty()) {
            Shark poll = q.poll();

            for (int i = 0; i < 4; i++) {
                int xf = poll.x + dx[i];
                int yf = poll.y + dy[i];

                if (xf >= 0 && xf < N && yf >= 0 && yf < N && !visited[xf][yf]) {

                    // 먹을 수 있는 물고기 발견
                    if (map[xf][yf] != 0 && poll.weight > map[xf][yf]) {
                        pq.add(new Shark(xf, yf, poll.weight, poll.cnt,poll.dist + 1));
                    } else if (map[xf][yf] != 0 && poll.weight < map[xf][yf]) {
                        continue;
                    }

                    // map[xf][yf] == 0이거나, 물고기가 있을 때 내 몸무게보다 같을 때
                    visited[xf][yf] = true;
                    q.add(new Shark(xf, yf, poll.weight, poll.cnt,poll.dist + 1));
                }
            }
        }
    }

    // 물고기를 먹는 함수
    private static Shark eatFish() {
        Shark poll = pq.poll();

        // 먹었다
        poll.cnt += 1;
        map[poll.x][poll.y] = 0;

        result += poll.dist;
        poll.dist = 0;

        if (poll.cnt == poll.weight) {
            poll.weight += 1;
            poll.cnt = 0;
        }
        return poll;
    }
}

4. 배운점

1. 우선순위 큐를 다시 한번 되새기는 계기가 됨
2. 모든 문제가 bfs, 혹은 dfs 한 번으로 끝날 수 있다는 고정관념 버리기 → 어떤 객체가 우선순위에 따라 특정 위치에 가고 나서 다시 우선순위를 측정하려할 때 bfs나 dfs 등을 여러 번 실행하는 경우를 생각하자.
   
   
   

5. 점수

30/100