[백준] 16236번 아기상어

🔔 문제

https://www.acmicpc.net/problem/16236

🎯 풀이방법

1. 상어 현재 위치에서 먹을 수 있는 물고기를 탐색한다. (BFS)
   1-1. 큐에서 현재 이동위치를 꺼낸다. 현재 이동위치에서 상하좌우로 탐색한다.
   1-2. 먹을 수 있는 물고기라면 큐와 식사리스트에 추가한다.
   1-3. 이동 가능(=사이즈가 동일하거나 0)하다면 큐에 추가한다.
   1-4. 큐가 empty일 때까지 1~3번 과정을 반복한다.

2. 먹을 수 있는 물고기가 있으면 가장 우선순위가 높은 물고기 한 마리를 먹는다.
   2-1. Fish를 주어진 조건대로 정렬한다. (우선순위 : 시간 빠름 > 맨위 > 맨왼쪽)
   2-2. Fish를 먹는다.
   2-3. 상어의 위치와 시간을 update한다.
   2-4. 식사리스트, 방문배열, 큐를 초기화하고 큐에다가 현재 상어를 추가한다.

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

🙄 예제 3

예제 3을 위의 알고리즘대로 진행하면 다음과 같다.

💡 이 문제를 통해 얻어갈 것

시뮬레이션 + BFS 문제

💻 Java code

메모리 22448KB, 시간 224ms

import java.io.*;
import java.util.*;

public class Main {
    static class Fish implements Comparable<Fish> {
        int row,col,time;
        public Fish(int row, int col, int time) {
            this.row = row;
            this.col = col;
            this.time = time;
        }

        @Override
        public int compareTo(Fish o) {   // (기준값).compareTo(비교대상)
            if(o.time == this.time) {
                if(o.row == this.row)
                    return this.col - o.col;
                else
                    return this.row - o.row;
            }
            return this.time - o.time;
        }
    }

    static int N, totalFish=0, eatenFish = 0;
    static boolean[][] visited;
    static int[][] map;

    // 상어
    static Fish shark;
    static int sharkSize = 2;

    static ArrayList<Fish> feedList = new ArrayList<>();
    static Queue<Fish> queue = new LinkedList<>();
    static int answer;

    // 상, 하, 좌, 우
    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};

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

        N = Integer.parseInt(br.readLine());
        visited = new boolean[N][N];
        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] == 9) {  // 상어 위치
                    shark = new Fish(i, j, 0);
                    map[i][j] = 0;
                }
                else if(map[i][j] >= 1)
                    totalFish++;
            }
        }

        queue.add(shark);
        visited[shark.row][shark.col] = true;

        while(true) {
            // 현재 위치에서 먹을 수 있는 물고기 탐색 (BFS)
            bfs();

            // 먹을 수 있는 물고기 중 가장 우선순위가 높은 거 먹기
            if(!feedList.isEmpty()) {
                eat();

                // 먹은 거 초기화
                feedList.clear();

                // 식사 끝났으면 방문배열 초기화
                queue.clear();
                visited = new boolean[N][N];

                // 다시 이동하는 큐에다가 현재 상어 추가
                queue.add(shark);
                visited[shark.row][shark.col] = true;
            } else {
                // 더 이상 먹을 수 있는 물고기가 없다면 탈출하기
                break;
            }
        }
        System.out.println(answer);
    }

    public static void bfs() {
        while(!queue.isEmpty()) {
            Fish now = queue.poll();
            int time = now.time;

            for(int i=0; i<4; i++) {
                int nr = now.row + dr[i];
                int nc = now.col + dc[i];

                // 갈 수 있는가?
                if(nr<0 || nr>=N || nc<0 || nc>=N || visited[nr][nc])
                    continue;

                Fish fish = new Fish(nr, nc, time+1);

                // 식사 가능
                if(map[nr][nc]>0 && map[nr][nc]<sharkSize) {
                    queue.add(fish);
                    visited[nr][nc] = true;
                    feedList.add(fish);
                }

                // 이동 가능 : 사이즈 동일 or 0
                if(map[nr][nc] == 0 || map[nr][nc] == sharkSize) {
                    queue.add(fish);
                    visited[nr][nc] = true;
                }
            }
        }
    }

    public static void eat() {
        // 먹을 물고기 리스트 중 맨위 좌측 먹기
        Collections.sort(feedList);
        Fish now = feedList.get(0);

        // 물고기 먹기
        eatenFish++;
        if(eatenFish == sharkSize) {
            sharkSize++;
            eatenFish = 0;
        }
        map[now.row][now.col] = 0;

        // 상어 update
        shark.row = now.row;
        shark.col = now.col;

        // 시간 update
        answer += now.time;
    }
}

💻 Python code

import sys
from collections import deque

input = sys.stdin.readline

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


n = int(input())
board = []

# 상어
shark_x, shark_y, shark_size = 0, 0, 2

for i in range(n):
    board.append(list(map(int, input().split())))
    for j in range(n):
        if board[i][j] == 9:
            shark_x = i
            shark_y = j
    
dx, dy = [0,0,1,-1], [1,-1,0,0]
count = 0


def biteFish(x, y, shark_size):
    distance = [[0]*n for _ in range(n)]
    visied = [[0]*n for _ in range(n)]
    
    queue = deque()
    queue.append((x,y))
    visied[x][y] = 1
    tmp = []
    
    while queue:
        cur_x, cur_y = queue.popleft()
        
        for i in range(4):
            nx, ny = cur_x + dx[i], cur_y + dy[i]
            
            if 0<=nx<n and 0<=ny<n and visied[nx][ny]==0:
                if board[nx][ny] <= shark_size:
                    queue.append((nx,ny))
                    visied[nx][ny] = 1
                    distance[nx][ny] = distance[cur_x][cur_y] + 1
                    
                    if board[nx][ny] < shark_size and board[nx][ny] != 0:
                        tmp.append((nx,ny,distance[nx][ny])) # 위치, 거리
                        
    # 우선순위: 거리가 가까운 물고기 > 가장 위에 있는 물고기 > 가장 왼쪽에 있는 물고기
    return sorted(tmp, key=lambda x:(-x[2],-x[0],-x[1]))


count = 0
result = 0
while True:
    eatable_fishes = biteFish(shark_x, shark_y, shark_size)
    
    # 더 이상 먹을 수 있는 물고기가 공간에 없다면 엄마상어에게 도움 요청
    if len(eatable_fishes)==0:
        break
    
    # Pick 먹을 물고기
    nx, ny, dist = eatable_fishes.pop()

    # 움직이는 칸수 = 시간
    result += dist
    board[shark_x][shark_y], board[nx][ny] = 0, 0
    
    # 상어좌표를 먹은 물고기 좌표로 이동
    shark_x, shark_y = nx, ny
    
    # 먹은 물고기 update
    count += 1
    if count == shark_size:
        shark_size += 1
        count = 0

print(result)