[백준 16236] 아기 상어 [Java]

문제

http://boj.ma/16236

요약

• 초기 아기 상어의 크기는 2이며, 자신과 크기가 동일하거나 작은 물고기는 지나갈 수 있다.
• 자신보다 크기가 작은 물고기만 먹을 수 있다.
• 탐색 종료 조건: 더 이상 먹을 수 있는 물고기가 없는 경우
• 먹을 수 있는 물고기가 2마리 이상일 경우 거리순으로 이동
• 거리가 동일하다면 (1)최상단 (2) 가장 왼쪽을 우선시한다.
• 이동에는 1초가 소모된다.
• 상어의 크기만큼 물고기를 먹으면 상어의 크기가 1 증가한다.

---

풀이 과정

아이디어

N ≤ 20이므로, BFS로 완전 탐색을 수행하며 다음에 먹을 수 있는 물고기를 찾으면 된다.

좌표를 정렬해 비교하는 방식은 실제 상어의 이동 경로를 고려하지 못하므로 적합하지 않다.

우선 상어와 물고기에 대한 클래스를 만들어주었다.

static class Shark {
    int x, y;
    int size = 2, eaten = 0, time = 0;
    Shark(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public void eat(Fish fish, int[][] board) {
        this.time += fish.dist;
        this.x = fish.x;
        this.y = fish.y;
        board[this.x][this.y] = EMPTY;

        this.eaten++;
        if (this.eaten == this.size) {
            this.eaten = EMPTY;
            ++this.size;
        }
    }
}
static class Fish {
    int x, y, dist;
    Fish(int x, int y, int dist) {
        this.x = x;
        this.y = y;
        this.dist = dist;
    }
    void update(int x, int y, int dist) {
        this.x = x;
        this.y = y;
        this.dist = dist;
    }
}

더 이상 먹을 물고기가 없을 때 까지 BFS를 수행하며 물고기를 찾으면 된다.

먹을 수 있는 물고기가 여러 마리일 수 있으므로, 탐색 방향을 위, 왼쪽 방향 먼저 탐색하도록 했다.

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

현재 영역에 위치한 물고기가 문제에서 제시한 조건(거리, 물고기 크기 등)을 만족하는지 검사하는 메서드를 다음과 같이 구현했다.

private static boolean canEat(int x, int y, int dist, Fish fish) {
    return dist < fish.dist || (dist == fish.dist
        && (x < fish.x || (x == fish.x && y < fish.y))
    );
}

현재 상어 정보를 입력 받고, 조건을 만족한다면 최종 물고기의 위치를 업데이트 하자.

private static Fish bfs(Shark shark) {
    boolean[][] visited = new boolean[N][N];
    Deque<int[]> queue = new ArrayDeque<>();
    queue.add(new int[]{shark.x, shark.y, 0});
    visited[shark.x][shark.y] = true;

    Fish result = new Fish(shark.x, shark.y, Integer.MAX_VALUE);
    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        int x = cur[0], y = cur[1], dist = cur[2];

        if (dist > result.dist) break;
        int fishSize = board[x][y];
        if (fishSize > 0 && fishSize < shark.size) {
            if (canEat(x, y, dist, result)) {
                result.update(x, y, dist);
            }
            continue;
        }

아니라면 fishSize가 0이거나 상어의 크기보다 크다면 다음 경로로 탐색을 계속하면 된다.

      for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            if (isValid(nx, ny) && !visited[nx][ny]) {
                if (board[nx][ny] > shark.size) continue;
                visited[nx][ny] = true;
                queue.add(new int[]{nx, ny,  dist + 1});
            }
        }
    }
    if (result.dist == Integer.MAX_VALUE) {
        return new Fish(-1, -1, -1);
    }
    return result;
}

성능 분석

• 시간 복잡도: $O(N^4)$
• 제출결과: Accepted / 120ms / 14,928KB

---

회고

문제의 조건과 풀이가 복잡해질수록, 단순한 절차적 코드보다는 클래스와 메서드를 활용한 객체 지향적인 구조가 자연스럽게 떠올랐다.

제한된 시간 안에 구현해야 하는 알고리즘 문제에서는 클래스를 정의하는 방식이 오히려 비효율적으로 느껴질 수 있지만, 여러 조건과 상태를 동시에 고려해야 하는 상황에서는 객체 지향적인 설계가 로직을 명확히 정리하는 데 큰 도움이 된다는 것을 깨달았다.

그 결과, 복잡한 규칙을 더 안정적으로 구현할 수 있었고, 코드의 가독성과 수정 용이성 역시 함께 개선되었다.

---

참고

문제

http://boj.ma/16236

16236번: 아기 상어

 

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/16236.java

problem-solving/baekjoon-online-judge/normal/16236.java at main · rogi-rogi/problem-solving