[BOJ : JAVA] 아기상어

문제 이해와 풀이 전략

문제 규칙 요약

1. 상어는 1칸당 1초의 시간이 소요된다.
2. 자신의 크기보다 큰 물고기가 있는 칸은 이동할 수 없다.
3. 크기가 같은 물고기는 지나갈 수 있으나 먹지는 못한다.
4. 상어가 크기만큼의 물고기를 먹으면 크기가 1 증가한다.
5. 먹을 수 있는 물고기가 없으면 종료된다.
6. 먹을 수 있는 물고기가 여러 마리일 경우:
   • 가장 가까운 물고기
   • 위쪽에 위치한 물고기
   • 왼쪽에 위치한 물고기 순으로 먹는다.
7. 물고기를 먹으면 해당 칸은 빈칸이 된다.

풀이 전략

1. BFS를 통해 현재 상어가 도달할 수 있는 모든 칸을 탐색하며 먹을 수 있는 물고기를 리스트에 추가한다.
2. 먹을 수 있는 물고기 리스트를 문제 조건에 맞게 정렬한다.
3. 가장 가까운 물고기를 먹고, 상어의 위치를 갱신하며 크기를 체크한다.
4. 더 이상 먹을 수 있는 물고기가 없으면 종료한다.

---

코드 설명

1. 좌표와 비용을 저장하는 Pair 클래스

좌표와 비용(이동 거리)을 함께 저장하기 위해 제네릭 타입을 활용한 Pair 클래스를 구현했다.

class Pair<T,G> {
    T first;
    G second;
    public Pair(T first, G second) {
        this.first = first;
        this.second = second;
    }
}

2. BFS 탐색 함수

BFS는 다음을 수행한다.

• 현재 상어가 도달할 수 있는 모든 칸을 탐색한다.
• 방문한 칸은 visited 배열에 표시한다.
• 먹을 수 있는 물고기를 edibleFish 리스트에 추가한다.

static void bfs() {
    reset(); // 방문 기록 초기화
    Queue<Pair<Pair<Integer, Integer>, Integer>> q = new LinkedList<>();
    q.add(new Pair<>(sharkPos, 0));
    visited[sharkPos.first][sharkPos.second] = true;

    while (!q.isEmpty()) {
        Pair<Pair<Integer, Integer>, Integer> current = q.poll();
        int x = current.first.first;
        int y = current.first.second;
        int cost = current.second;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            int nCost = cost + 1;

            if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if (visited[nx][ny]) continue;
            if (map[nx][ny] > sharkSize) continue;

            visited[nx][ny] = true;

            if (map[nx][ny] != 0 && map[nx][ny] < sharkSize) {
                edibleFish.add(new Pair<>(new Pair<>(nx, ny), nCost));
            }

            q.add(new Pair<>(new Pair<>(nx, ny), nCost));
        }
    }
}

3. 먹을 물고기 선택

BFS로 얻은 edibleFish 리스트를 문제 조건에 따라 정렬한다.

• 우선 순위: 거리 → y좌표 → x좌표

Collections.sort(edibleFish, new Comparator<Pair<Pair<Integer, Integer>, Integer>>() {
    @Override
    public int compare(Pair<Pair<Integer, Integer>, Integer> o1, Pair<Pair<Integer, Integer>, Integer> o2) {
        int comp2 = o1.second.compareTo(o2.second);
        if (comp2 != 0) return comp2;

        int comp3 = o1.first.first.compareTo(o2.first.first);
        if (comp3 != 0) return comp3;
        return o1.first.second.compareTo(o2.first.second);
    }
});

---

주요 함수 흐름

main 함수

1. 입력값을 받아 맵과 상어의 초기 위치를 설정한다.
2. BFS를 반복하며 먹을 수 있는 물고기가 없을 때까지 반복한다.
3. 총 이동 시간을 출력한다.

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int eat = 0;
    int totalDist = 0;

    N = sc.nextInt();
    map = new int[N][N];
    visited = new boolean[N][N];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            map[i][j] = sc.nextInt();
            if (map[i][j] == 9) {
                sharkPos = new Pair<>(i, j);
                map[i][j] = 0; // 상어의 초기 위치
            }
        }
    }

    while (true) {
        bfs();
        if (edibleFish.isEmpty()) break;

        Pair<Pair<Integer, Integer>, Integer> p = edibleFish.get(0);
        eat++;

        if (eat == sharkSize) {
            eat = 0;
            sharkSize++;
        }

        map[p.first.first][p.first.second] = 0;
        sharkPos = new Pair<>(p.first.first, p.first.second);
        totalDist += p.second;
    }

    System.out.println(totalDist);
}