[백준] 16236번 / Java / 아기상어 - BFS 풀이

문제 - (https://www.acmicpc.net/problem/16236)

아기상어가 상좌우하로 이동하면서 자신이 먹을 수 있는 물고기를 먹다가 더이상 먹을 수 있는 물고기가 없을 때 걸린 시간을 리턴하는 문제다.

 

아기상어가 물고기를 먹기 위한 조건이 있는데,

1. 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다. == 종료조건

2. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.

3. 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.

• 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.
• 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

3-1을 통해 현재 상어의 위치에서 먹을 수 있는 물고기까지의 "최단거리"를 구해야 하는 것을 알 수 있고, 최단거리는 BFS를 사용하는 것이 좋으므로 (굳이 DFS를 사용해서 모든 경우를 살펴볼 필요 없이, BFS로 최단거리 내에 먹을 수 있는 물고기를 발견하면 더이상 진행하지 않고 그 물고기를 먹으면 되므로) 어떤 알고리즘을 사용할 지 방향을 정할 수 있다.

 

3-2를 만족하기 위해 나는 우선순위 큐를 사용했다.

static class Pos {
        int y;
        int x;
        int distance;

        Pos(int y, int x, int distance) {
            this.y = y;
            this.x = x;
            this.distance = distance;
        }
}

Queue<Pos> q = new PriorityQueue<>((o1, o2) -> {
	if (o1.distance == o2.distance) {
		if (o1.y == o2.y) return Integer.compare(o1.x, o2.x);
		return Integer.compare(o1.y, o2.y);
	}
	return Integer.compare(o1.distance, o2.distance);
});

현재 상어의 위치로부터 거리가 같은 물고기인 경우 x, y 좌표를 확인하여 큐에 삽입한다.

- 가장 위에 있는 물고기 => y좌표가 더 작음

- 가장 왼쪽에 있는 물고기 => x좌표가 더 작음

---

📌배운 것

• 상어가 이동할 위치를 큐에 담을 때, 현재 상어와의 거리, 좌표를 기록할 수 있는 클래스를 생성하기
• 최단거리 알고리즘이 필요할 땐 BFS 사용하기

---

😅실수

• 상어를 '상 좌 우 하'로 이동시킬 때마다 이전에 왔던 곳은 visited에 표시해두어 다시 접근하지 않도록 한다.
  ex) 1,1에서 0,1로 이동했을 때, 다시 1,1로 가서 무한반복되는 경우
• 한 번의 BFS로 답을 찾으려고 하니 어려웠던 문제다. 상어의 위치에서 가장 가까운 먹을 수 있는 물고기를 찾는 BFS를 진행하고, 발견한다면 상어를 그 위치로 이동시키고 그 위치에서 다시 BFS를 시작한다는 로직을 생각할 수 있어야 한다.
  이때, "다시 시작"하는 것이므로 초기화해야 할 것들은 다시 초기화한다. visited라던지, 큐에 담겨져있는 것들을 비운다던지..

 

 

참고: https://mygumi.tistory.com/339 [마이구미의 HelloWorld]

---

코드

public class BabyShark_RIGHT {
    static int n;
    static int sharkY;
    static int sharkX;
    static int sharkSize = 2;
    static int eatCnt;
    // 상좌우하 dy dx
    static int[] dy = {-1, 0, 0, 1};
    static int[] dx = {0, -1, 1, 0};
    static int answer;
    static boolean[][] visited;

    static class Pos {
        int y;
        int x;
        int distance;

        Pos(int y, int x, int distance) {
            this.y = y;
            this.x = x;
            this.distance = distance;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        n = Integer.parseInt(br.readLine());
        int[][] 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] != 0) {
                    if (map[i][j] == 9) {
                        sharkY = i;
                        sharkX = j;
                        map[i][j] = 0; // 처음 상어의 위치는 0으로 초기화
                    }
                }
            }
        }

        Queue<Pos> q = new PriorityQueue<>((o1, o2) -> {
            if (o1.distance == o2.distance) {
                if (o1.y == o2.y) return Integer.compare(o1.x, o2.x);
                return Integer.compare(o1.y, o2.y);
            }
            return Integer.compare(o1.distance, o2.distance);
        });

        // 상어의 처음 위치 큐에 삽입
        q.add(new Pos(sharkY, sharkX, 0));
        visited = new boolean[n][n];
        visited[sharkY][sharkX] = true;

        while (!q.isEmpty()) {
            Pos curPos = q.poll(); // 상어의 현재 위치

            for (int i = 0; i <= 3; i++) {
                int moveY = curPos.y + dy[i];
                int moveX = curPos.x + dx[i];
                if (!(moveY < n && moveX < n && moveY >= 0 && moveX >= 0)) continue;
                if (visited[moveY][moveX]) continue;
                visited[moveY][moveX] = true;

                if (map[moveY][moveX] <= sharkSize)
                    q.add(new Pos(moveY, moveX, curPos.distance + 1));
            }

            if (q.peek() != null) {
                Pos peek = q.peek();
                if (map[peek.y][peek.x] < sharkSize && map[peek.y][peek.x] > 0) {
                    // 큐에 담긴 pos에 있는 물고기가 상어보다 작으면 물고기를 먹는다
                    eatCnt++;
                    if (eatCnt == sharkSize) {
                        sharkSize++;
                        eatCnt = 0;
                    }
                    map[peek.y][peek.x] = 0;

                    // 큐를 비우고 상어를 peek 위치로 이동
                    q.clear();
                    q.add(new Pos(peek.y, peek.x, 0));
                    answer += peek.distance;
                    visited = new boolean[n][n];
                    visited[peek.y][peek.x] = true;
                }
            }
        }

        System.out.println(answer);
    }
}