[알고리즘 / 백준] 16236 - 아기 상어

www.acmicpc.net/problem/16236

16236번: 아기 상어

 

문제는 위와 같으며, 아기 상어 문제는 BFS 를 활용하여 문제를 풀 수 있습니다.

 

1. 현재 상어의 위치에서 가장 가까이에 있는 먹을 수 있는 물고기가 있는지 확인합니다. (BFS 사용)

2. 먹을 수 있는 물고기가 없다면, 그대로 반복을 종료하고 지금까지 물고기를 먹기 위해 이동한 시간(time 변수 값)을 출력합니다.

3. 먹을 수 있는 물고기가 있다면,

    (1) 먹은 물고기 수를 하나 증가시키고

    (2) 먹은 물고기 수와 상어의 크기가 같은 경우, 상어의 크기를 + 1 하고 먹은 물고기 수를 다시 0으로 초기화 합니다.

4. 위 과정을 먹을 수 있는 물고기가 없을 때까지 반복합니다.

 

현재 상어의 위치에서 먹을 수 있는 가장 가까운 물고기를 확인하는 방법(BFS)은 다음과 같습니다.

 

1. 현재 상어의 위치에서 이동할 수 있는 칸의 정보를 담는 우선순위 큐를 생성하고, [현재 위치까지 상어가 이동하는데 걸린 시간, 현재 위치의 x, 현재 위치의 y] 형태의 데이터를 저장합니다. 이 우선순위 큐는 (1) 현재 위치까지 상어가 이동하는데 걸린 시간 (2) x 좌표 (3) y 좌표를 기준으로 우선순위를 확인합니다.

2. 현재 상어의 위치를 우선순위 큐에 넣고 우선 순위 큐가 빌 때까지 아래 과정(3, 4, 5)을 반복합니다.

3. 우선 순위 큐에서 현재 위치에 대한 정보를 꺼냅니다.

4. 현재 위치에 물고기가 있고 그 물고기의 크기가 상어의 크기보다 작아서 물고기를 먹을 수 있는 경우

    (1) 현재 위치의 물고기를 먹기 위해 상어가 이동한 시간을 전체 시간(time 변수)에 더하고

    (2) 상어의 위치를 현재 위치로 변경합니다.

    (3) 현재 위치에는 더 이상 물고기가 존재하지 않으므로 물고기 정보를 담는 이차원 배열의 값을 0으로 수정합니다.

    (4) 상어의 위치에서 가장 가까운 물고기를 먹었으므로 true 를 리턴하고 bfs 메소드를 종료합니다.

5. 현재 위치에 물고기가 없거나 먹을 수 없는 경우에는 상, 좌, 우, 하 위치로 순서대로 이동하면서 아래와 같은 내용을 확인합니다.

    (1) 다음 이동할 위치가 구역 내에 있고

    (2) 다음 위치에 물고기가 없거나 상어보다 작거나 같으며(이동할 수 있으며) 아직 다음 위치를 방문한 적이 없는 경우

    (3) [다음 위치까지 이동하는데 걸리는 시간(현재 위치까지 이동하는데 걸리는 시간 + 1), 다음 위치 x, 다음 위치 y] 데이터를 우선 순위

         큐에 저장하고 다음 위치를 방문한 것으로 처리합니다.

6. 우선 순위 큐에 데이터가 없을 때까지(현재 상어 위치에서 갈 수 있는 모든 위치를 다 방문한 경우) 반복할 동안 먹을 수 있는 물고기를 찾지 못하면 false 를 리턴하고 bfs 메소드를 종료합니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin
import heapq

dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]


def bfs(x, y):
    global time, shark_x, shark_y
    queue = []
    heapq.heappush(queue, [0, x, y])

    while queue:
        c, cx, cy = heapq.heappop(queue)

        if 0 < fish[cx][cy] < shark_weight:  # 물고기를 먹은 경우
            time += c  # 물고기 먹는데 걸린 시간 추가
            shark_x = cx  # 먹은 물고기 위치로 상어 이동 (x)
            shark_y = cy  # 먹은 물고기 위치로 상어 이동 (y)
            fish[cx][cy] = 0  # 먹은 물고기 위치 0으로 수정
            return True

        # 물고기를 못 먹은 경우 다음 물고기 위치로 이동
        for d in range(4):
            nx = cx + dx[d]
            ny = cy + dy[d]

            if 0 <= nx < n and 0 <= ny < n:  # 다음 위치가 공간 내에 있고
                if fish[nx][ny] <= shark_weight and not visited[nx][ny]:  # 물고기의 크기가 상어보다 작거나 같으면서 아직 해당 위치로 이동하지 않은 경우
                    heapq.heappush(queue, [c + 1, nx, ny])  # [해당 위치까지 이동한 시간, 다음 x 위치, 다음 y 위치] 저장
                    visited[nx][ny] = True  # 다음 위치를 방문한 것으로 처리

    return False  # 결과적으로 더이상 먹을 물고기가 없는 경우


n = int(stdin.readline())

shark_x = 0
shark_y = 0
shark_weight = 2
eat_fish = 0

fish = list()
for i in range(n):
    tmp = list(map(int, stdin.readline().split()))
    if 9 in tmp:
        shark_x = i
        shark_y = tmp.index(9)
        tmp[shark_y] = 0  # 원래 상어의 위치를 물고기가 없는 것으로 표시
    fish.append(tmp)

time = 0
while True:
    visited = [[False] * n for _ in range(n)]
    visited[shark_x][shark_y] = True

    if not bfs(shark_x, shark_y):  # 먹을 물고기가 없는 경우 종료
        break

    eat_fish += 1  # 먹은 물고기 수 증가

    if eat_fish == shark_weight:  # 먹은 물고기와 아기 상어의 무게가 같아질 때
        shark_weight += 1  # 무게를 증가시키고
        eat_fish = 0  # 먹은 물고기 수 초기화

print(time)

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {
    private static int[] dx = {-1, 0, 0, 1};
    private static int[] dy = {0, -1, 1, 0};

    private static int shark_x = 0;
    private static int shark_y = 0;
    private static int shark_weight = 2;

    private static int n;
    private static int[][] fish;
    private static boolean[][] visited;

    private static int time = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        fish = new int[n][n];
        for (int i = 0; i < n; i++) {
            int[] tmp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int j = 0; j < tmp.length; j++) {
                if (tmp[j] == 9) {  // 상어의 위치를 알게되는 경우
                    shark_x = i;  // 상어 위치 저장 (x)
                    shark_y = j;  // 상어 위치 저장 (y)
                    tmp[j] = 0;  // 원래 상어 위치에는 물고기가 없으므로 0으로 수정
                }
            }
            fish[i] = tmp;  // 구역 내 물고기 위치 저장
        }

        int numOfEatenFish = 0;

        while (true) {
            visited = new boolean[n][n];
            visited[shark_x][shark_y] = true;

            if (!bfs(shark_x, shark_y)) {  // 더 이상 잡아먹을 물고기가 없는 경우
                break;
            }

            numOfEatenFish += 1;

            if (numOfEatenFish == shark_weight) {  // 먹은 물고기 수가 상어의 크기와 같은 경우
                shark_weight += 1;  // 상어 크기 증가
                numOfEatenFish = 0;  // 먹은 물고기 수 초기화
            }
        }

        System.out.println(time);  // 엄마 상어에게 도움 요청하기까지 최종 시간 출력
    }

    private static boolean bfs(int x, int y) {
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] t1, int[] t2) {
                return t1[0] - t2[0] != 0 ? t1[0] - t2[0] : (t1[1] - t2[1] != 0 ? t1[1] - t2[1] : t1[2] - t2[2]);
            }
        });
        queue.offer(new int[]{0, x, y});

        while (!queue.isEmpty()) {
            int[] current = queue.poll();

            if (fish[current[1]][current[2]] > 0 && fish[current[1]][current[2]] < shark_weight) {  // 현재 위치의 물고기를 먹을 수 있는 경우
                time += current[0];  // 지금까지 이동하는데 걸린 시간 추가
                shark_x = current[1];  // 상어 위치 이동 (x)
                shark_y = current[2];  // 상어 위치 이동 (y)
                fish[current[1]][current[2]] = 0;  // 원래 있던 물고기가 먹혔으므로 물고기가 없음(0)으로 변경
                return true;
            }

            for (int i = 0; i < 4; i++) {
                int nx = current[1] + dx[i];
                int ny = current[2] + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < n) {  // 다음 이동 위치가 구역 내에 있고
                    if (fish[nx][ny] <= shark_weight && !visited[nx][ny]) {  // 다음 이동 위치가 상어의 무게보다 작거나 같고 아직 방문한 적이 없는 경우
                        queue.offer(new int[]{current[0] + 1, nx, ny});  // 다음 위치 우선순위 큐에 추가
                        visited[nx][ny] = true;  // 다음 위치를 방문한 것으로 처리
                    }
                }
            }
        }
        return false;
    }
}