Algorithm / / 2025. 3. 30. 14:23

[16236] 아기 상어 문제 분석 및 리뷰

1. 문제 분석

 

목표: N×N 공간에서 아기 상어가 자신의 크기보다 작은 물고기를 잡아먹으며 성장하는 과정을 시뮬레이션하여, 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 총 시간을 계산합니다.

 

제약 조건:

 

  • 공간 크기 N: 2 ≤ N ≤ 20
  • 물고기 크기: 1 ~ 6
  • 아기 상어 초기 크기: 2
  • 아기 상어 이동: 상하좌우 인접한 한 칸씩, 1초 소요
  • 아기 상어 이동 규칙: 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없음
  • 아기 상어 먹이 규칙: 자신의 크기보다 작은 물고기만 먹을 수 있음 (크기가 같은 물고기는 먹을 수 없지만 지나갈 수 있음)
  • 먹이 선택 규칙:
    1. 더 이상 먹을 수 있는 물고기가 없으면 종료.
    2. 먹을 수 있는 물고기가 1마리라면 그 물고기를 먹으러 감.
    3. 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 감.
    4. 거리가 가까운 물고기가 여러 마리라면, 가장 위에 있는 물고기를 먹음.
    5. 가장 위에 있는 물고기가 여러 마리라면, 가장 왼쪽에 있는 물고기를 먹음.
  • 먹는 시간: 0초 (이동과 동시에 먹음)
  • 성장 조건: 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가

 

핵심:

  • BFS (Breadth-First Search): 아기 상어로부터 가장 가까운 먹을 수 있는 물고기를 찾는 데 필수적인 알고리즘입니다.
  • 시뮬레이션: 문제에서 제시된 아기 상어의 행동 규칙을 정확하게 구현하여 시간의 흐름에 따른 상태 변화를 추적해야 합니다.
  • 우선순위 큐 (Implicit): 먹을 수 있는 물고기가 여러 마리일 때, 거리, 위치(위, 왼쪽) 순으로 우선순위를 정하여 선택해야 합니다. 이는 BFS 과정에서 자연스럽게 처리될 수 있습니다.

 

 

2. 제시된 Java 코드 리뷰

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {

    private static int N;
    private static int[][] grid;
    private static boolean[][] visited;

    private static int sharkSize = 2, eatCnt = 0, addTime = 0;
    private static int sy, sx;

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

    public static void main(String[] args){
        input();

        int totalTime = 0;
        while (moveNext()) {
            totalTime += addTime;
        }

        System.out.println(totalTime);
    }

    private static boolean moveNext() {
        for (int i = 0; i < N; i++)
            Arrays.fill(visited[i], false);

        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{sy, sx});

        boolean canEat = false;
        addTime = -1;
        int ny = Integer.MAX_VALUE;
        int nx = ny;

        while (!q.isEmpty() && !canEat) {
            int size = q.size();

            for (int i = 0; i < size; i++) {
                int[] elem = q.poll();
                int y = elem[0];
                int x = elem[1];

                if (y < 0 || y >= N || x < 0 || x >= N || grid[y][x] > sharkSize || visited[y][x]) continue;
                visited[y][x] = true;
                if (grid[y][x] > 0 && grid[y][x] < sharkSize) {
                    canEat = true;
                    if (y < ny) {
                        ny = y;
                        nx = x;
                    }else if (y == ny && x < nx) {
                        nx = x;
                    }
                }

                for (int d = 0; d < 4; d++)
                    q.offer(new int[]{y + dy[d], x + dx[d]});
            }
            ++addTime;
        }
        if (canEat) {
            sy = ny;
            sx = nx;
            grid[sy][sx] = 0;
            if (sharkSize == ++eatCnt) {
                sharkSize++;
                eatCnt = 0;
            }
        }

        return canEat;
    }


    private static void input() {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            grid = new int[N][N];
            visited = new boolean[N][N];

            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    int next = Integer.parseInt(st.nextToken());
                    grid[i][j] = next;
                    if (next == 9) {
                        sy = i;
                        sx = j;
                        grid[i][j] = 0;
                    }
                }
            }
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
    }
}

 

제시된 Java 코드는 문제의 요구사항을 비교적 정확하게 구현하고 있습니다. 주요 부분에 대한 리뷰는 다음과 같습니다.

 

장점:

 

  • BFS를 활용한 최단 거리 탐색: moveNext() 함수에서 BFS를 사용하여 아기 상어의 현재 위치에서 먹을 수 있는 물고기까지의 최단 거리를 효율적으로 탐색합니다.
  • 먹이 선택 우선순위 구현: BFS 과정에서 먹을 수 있는 물고기를 발견했을 때, 거리, y좌표, x좌표 순으로 비교하여 가장 적합한 물고기를 선택하는 로직이 잘 구현되어 있습니다.
  • 상어 성장 로직 구현: eatCnt 변수를 사용하여 먹은 물고기 수를 추적하고, sharkSize와 비교하여 상어의 크기를 증가시키는 로직이 정확합니다.
  • 입력 처리: input() 함수에서 입력 데이터를 올바르게 파싱하고 아기 상어의 초기 위치를 찾는 로직이 구현되어 있습니다.
  • 종료 조건: 더 이상 먹을 수 있는 물고기가 없을 때 moveNext() 함수가 false를 반환하여 시뮬레이션을 종료하는 로직이 적절합니다.

 

개선점 및 고려 사항:

 

  • 변수명: 일부 변수명(sy, sx, ny, nx)이 다소 축약되어 있어 코드의 가독성을 약간 저하시킬 수 있습니다. sharkY, sharkX, targetY, targetX와 같이 더 명확한 이름을 사용하는 것을 고려해볼 수 있습니다.
  • 주석: 코드의 핵심 로직에 대한 주석이 조금 더 추가되면 이해하기 쉬울 것입니다. 특히 BFS 내부 루프나 먹이 선택 로직에 대한 설명이 있으면 좋습니다.
  • BFS 종료 조건: 현재 BFS는 큐가 빌 때까지 탐색하거나 먹을 수 있는 물고기를 찾으면 종료됩니다. 만약 모든 먹을 수 있는 물고기를 찾고 그중 최적의 물고기를 선택하는 방식으로 구현했다면, BFS 종료 조건을 명확히 하는 것이 좋습니다. 현재 코드는 BFS 과정에서 가장 먼저 발견된 먹을 수 있는 물고기 중 우선순위가 가장 높은 물고기를 선택하는 방식입니다. 이는 효율적이지만, 모든 거리에 대해 탐색하지 않을 수 있습니다. 하지만 문제 조건상 최단 거리를 우선하므로 현재 방식이 적절합니다.
  • 코드 구조: moveNext() 함수가 다소 길어질 수 있습니다. 먹이 탐색 로직과 먹이 섭취 및 상어 성장 로직을 분리하여 함수를 더 작고 응집력 있게 만들 수 있습니다.

 

 

3. 개선 방안

 

위의 고려 사항을 바탕으로 몇 가지 개선 방안을 제시합니다.

 

  1. 변수명 개선:
    • sy → sharkY
    • sx → sharkX
    • ny → targetY
    • nx → targetX
  2. 주석 추가:
    • BFS 시작 시점, 큐에 neighbor를 추가하는 부분, 먹을 수 있는 물고기를 찾았을 때의 조건 등에 대한 주석을 추가합니다.
    • 먹이 선택 우선순위(거리, 위, 왼쪽)에 대한 주석을 명시합니다.
  3. 함수 분리 (선택 사항):
    • findNearestEdibleFish() 함수를 만들어 BFS를 수행하고 가장 가까운 먹을 수 있는 물고기의 좌표와 거리를 반환하도록 합니다.
    • eatFishAndGrow() 함수를 만들어 물고기를 먹고 상어의 상태를 업데이트하는 로직을 분리합니다.
    // 개선된 moveNext() 함수 예시
private static boolean moveNext() {
    // ... 초기화 ...

    int[] target = findNearestEdibleFish(); // 가장 가까운 먹을 수 있는 물고기 탐색

    if (target == null) {
        return false; // 더 이상 먹을 수 있는 물고기가 없음
    }

    int targetY = target[0];
    int targetX = target[1];
    addTime = target[2]; // 이동 시간

    eatFishAndGrow(targetY, targetX); // 물고기 먹고 상어 성장

    return true;
}

private static int[] findNearestEdibleFish() {
    // ... BFS 로직 ...
    // 먹을 수 있는 물고기를 찾으면 [y, x, distance] 형태의 배열 반환
    // 찾지 못하면 null 반환
}

private static void eatFishAndGrow(int y, int x) {
    sharkY = y;
    sharkX = x;
    grid[sharkY][sharkX] = 0;
    eatCnt++;
    if (sharkSize == eatCnt) {
        sharkSize++;
        eatCnt = 0;
    }
}

4. 다른 알고리즘

 

문제의 핵심은 최단 거리 탐색과 정해진 규칙에 따른 시뮬레이션입니다. 따라서 제시된 BFS 기반의 접근 방식이 가장 자연스럽고 효율적인 방법이라고 할 수 있습니다.

 

다른 알고리즘을 고려해본다면 다음과 같은 것들이 있을 수 있지만, 현재 문제의 제약 조건과 목표를 고려했을 때 BFS보다 효율적이거나 더 나은 해결책이라고 보기는 어렵습니다.

 

  • 다익스트라 알고리즘: 가중치가 없는 그래프에서의 최단 경로는 BFS로 충분히 찾을 수 있으므로, 다익스트라 알고리즘을 사용할 필요는 없습니다.
  • A* 알고리즘: 휴리스틱 함수를 정의하기 어렵고, 매번 목표 지점(먹을 수 있는 물고기)이 바뀌기 때문에 A* 알고리즘의 장점을 활용하기 어렵습니다.
  • DFS (Depth-First Search): 최단 거리를 보장하지 않으므로 적합하지 않습니다.

 

결론적으로, 제시된 Java 코드는 문제 해결에 적합한 알고리즘(BFS)을 사용하고 있으며, 구현도 전반적으로 잘 되어 있습니다. 언급된 개선 사항들을 적용하여 코드의 가독성과 유지보수성을 높일 수 있습니다.

 

 

5. 추가적인 고려 사항

 

  • 최적화: N의 크기가 작기 때문에 현재의 BFS 기반 솔루션으로 충분히 시간 내에 문제를 해결할 수 있습니다. 만약 N의 크기가 더 커진다면, 매번 BFS를 수행하는 대신 이동 가능한 영역을 미리 계산하거나 다른 최적화 기법을 고려해야 할 수 있습니다. 하지만 현재 문제에서는 불필요한 최적화일 가능성이 높습니다.
  • 테스트 케이스: 다양한 크기의 맵, 다양한 물고기 분포, 아기 상어의 초기 위치 등 다양한 테스트 케이스를 통해 코드의 정확성을 검증하는 것이 중요합니다. 문제에 제시된 예제 입력 외에도 여러 가지 경우를 생각하여 테스트해보세요.

 

이 분석과 리뷰가 문제 해결 및 코드 개선에 도움이 되기를 바랍니다.

'Algorithm' 카테고리의 다른 글

[LeetCode SQL] 185: Department Top Three Salaries - 코드 리뷰 및 분석  (0) 2025.03.30
[17144] 미세먼지 안녕! 문제 분석 및 리뷰  (0) 2025.03.30
[LeetCode SQL] 585: Investments in 2016 - 코드 리뷰 및 분석  (0) 2025.03.29
[LeetCode SQL] 1321: Restaurant Growth 코드 리뷰 및 분석  (0) 2025.03.27
[LeetCode SQL] 1341: Movie Rating 코드 리뷰 및 분석  (0) 2025.03.27
  • 네이버 블로그 공유
  • 네이버 밴드 공유
  • 페이스북 공유
  • 카카오스토리 공유
Algorithm 관련 글
글 더보기

티스토리툴바