백준 16236번 아기상어

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Baby_Shark {
    static int N;
    static int[][] map;
    static int[]shark;
    static int[] dr = {-1,0,0,1};
    static int[] dc = {0,-1,1,0};
    static int time = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        shark = new int[2];
        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[0] = i;
                    shark[1] = j;
                }
            }
        }
        eat(shark[0],shark[1],2,0);
        System.out.println(time);
    }
    
    public static void eat(int row,int col,int sharkSize,int foodcnt){
        Queue<int[]> que = new LinkedList<>();
        boolean[][] visited = new boolean[N][N];
        int [][] timecnt = new int[N][N];
        List<int[]> list = new ArrayList<>();
        int min = Integer.MAX_VALUE;
        visited[row][col] = true;
        que.add(new int[]{row,col});
        while (!que.isEmpty()){
            int[] current = que.poll();
            int crow = current[0];
            int ccol = current[1];
            for (int i = 0; i < 4; i++) {
                int nrow = crow + dr[i];
                int ncol = ccol + dc[i];
                if(nrow<0||ncol<0||nrow>=N||ncol>=N)
                    continue;
                if(!visited[nrow][ncol]&&map[nrow][ncol]<=sharkSize){
                    timecnt[nrow][ncol] = timecnt[crow][ccol]+1;
                    if(map[nrow][ncol]<sharkSize&&map[nrow][ncol]!=0&&min>=timecnt[nrow][ncol]) {
                        min = timecnt[nrow][ncol];
                        list.add(new int[] {nrow,ncol});
                    }
                    visited[nrow][ncol] = true;
                    que.add(new int[]{nrow,ncol});
                }
            }
        }
        if(list.isEmpty()) return;
        int minrow = Integer.MAX_VALUE;
        int mincol = Integer.MAX_VALUE;
        for (int i = 0; i < list.size(); i++) {
            int[] food = list.get(i);
            if(food[0]<minrow){
                minrow = food[0];
                mincol = food[1];
            }else if(food[0]==minrow){
                if(food[1]<mincol){
                    mincol = food[1];
                }
            }
        }
        map[row][col] = 0;
        map[minrow][mincol] = 9;
        shark[0] = minrow;
        shark[1] = mincol;
        foodcnt++;
        if(foodcnt==sharkSize){
            sharkSize++;
            foodcnt = 0;
        }
        time += timecnt[minrow][mincol];
        eat(shark[0],shark[1],sharkSize,foodcnt);
    }
}

문제 조건

아기상어 초기 크기 = 2

조건
자기보다 큰 물고기 있는칸 지나갈 수 없다.
자기랑 같은 크기는 지나갈 수 있다.
자기보다 작은 크기는 지나가며 먹는다.

이동 방법
1. 맵에 먹을 수 있는 물고기 더이상 없다면 끝
2. 맵에 먹을 수 있는 물고기 1마리라면 그 물고기 먹으러 감
3. 맵에 먹을 수 있는 물고기 여러마리라면, 가까운 물고기 먹으러 감
가장 가까운 물고기가 여러마리면, 가장 위쪽 물고기, 그것도 여러마리면 그중에 가장 왼쪽에 있는 물고기 먹음

크기
자신의 크기 만큼의 물고기를 먹을때 마다 크기 1 증가

풀이 방법

크게보면 상어가 먹이 하나를 찾으러 갈때는 bfs탐색을 하고, 먹이를 먹을 수 없을때까지 재귀함수를 호출하는 형식이다.

1. 상어의 위치, 크기, 커진뒤 먹은 먹이수를 eat() 함수에 넘긴다.
2. 먹이를 먹으러 가는 시간을 구하기 위해 timecnt배열을 생성했고,
   timecnt[nrow][ncol] = timecnt[crow][ccol]+1; 를 통해 이동할때마다 시간을 기록해 주었다.
3. 가장 가까운먹이에 도달한 시간을 min에 넣어주고, 같은시간동안 먹을 수 있는 먹이의 좌표를 전부 list에 담아준다.
4. list가 비었으면 먹을수 있는 먹이가 없다는 뜻이므로 함수를 종료한다.
5. list를 탐색하면서 가장 위쪽, 그중에서 왼쪽에 있는 먹이를 먹는다.
6. 먹이가 있던 좌표를 0으로 바꿔주고, 상어의 위치를 해당 좌표로 바꾼다.
7. foodcnt를 증가 시켜주고, foodcnt가 상어의 크기와 같아지면 상어의 크기를 증가시키고 foodcnt를 0으로 초기화 한다.
8. 해당 먹이를 먹으러 가면서 걸린 시간을 총 시간에 더해준다.
9. 상어의 위치, 크기, foodcnt를 다시 eat()함수에 넘기면서 다음먹이를 찾으러 간다.

후기

예전에 시도했을때, 몇시간동안 붙잡고 풀이를 봐도 이해를 못해서 못풀던 문제였다.

이번에도 "가장 위쪽, 그중에 가장 왼쪽" 이 조건 때문에 한번막혔다.
애초에 dr,dc의 순서로만 해결할 수 있는 문제가 아니었는데 dr,dc로만 해결하려고 하니 계속 막혔던거 같다.
같은 시간동안 먹는 먹이를 list에 담고 list를 다시 탐색하는 방법을 이번에 떠올려서 다행이다.

먹이먹는 시간을 좌표상의 거리로 구한다거나(돌아갈경우 틀림),
크기가 작은 먹이가 있어도 못 먹는 경우도 있는데 그걸 고려안했다거나
하는 실수도 있었다.