[백준] 아기 상어

얘 때문에 자존감 떨어짐....처음에 문제 이해를 못하겠어서 멘붕이 왔었음...

 

처음 사이즈는 2부터 시작한다.

물고기 <= 자기 사이즈 이면 지나갈 수 있다. 거기서 물고기 크기 < 자기 사이즈이면 먹을 수 있다. 같으면 지나갈 수만 있다.

만약 자기 사이즈 == 먹은 물고기 크기 이면 자기 사이즈를 +1한다.

 

가장 중요한 점은 아기상어의 먹이 위치 지정이다.

바로 이 부분인데, 처음에 보면 멘붕이 오고 여러번 봐도 멘붕이 온다 천천히 봐도 멘붕이 온다. 

그런데 그냥 우선순위 큐를 생각하면 된다.

보통 BFS에서는 좌표를 Deque (자바기준) 에 넣어서 사용하지만 이 친구의 경우에는 가야하는 좌표가 우선적으로 있으므로 우선순위 큐를 사용하면 된다.

1. 우선순위 큐 사용하기 

우선순위 큐의 가장 처음 정렬 기준

1. 가장 왼쪽에 있는 먹이

2. 가장 위에 있는 먹이

3. 가장 가까운 먹이

 

처음에 거리가 가까운 것을 기준으로 정렬한다. 하지만 거리가 가까운게 여러개면 더 위쪽(행) 에 있는 것을 우선순위로 지정한다. 만약 같은 행에 위치해있다면 그 중에서도 왼쪽(열의 크기가 작은 경우) 를 따지면 된다.

 

이해가 안 가서 그림으로 그려보면 아마 이해가 간다..

 

이렇게 우선순위 큐를 람다식으로 정의해보면 코드가 짜진다.

    PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
                if (o1[2] != o2[2]) {
                    return o1[2] - o2[2];
                } else if (o1[0] != o2[0]) {
                    return o1[0] - o2[0];
                }
                return o1[1] - o2[1];
});

2.  먹이를 찾으면 다시 방문 배열과 우선순위 큐를 초기화 해주기

int[] current = pq.poll();
int x = current[0];
int y = current[1];
int dir = current[2];
if (map[x][y] > 0 && map[x][y] < size) { //자기보다 크기가 작으면
    eat++; //먹어치우고
    flag = true;
    map[x][y] = 0;
    time += dir; //이동시간 증가
    r = x;
    c = y; //아기상어 위치 업데이트
    break; //첫번째 먹이를 먹으면, 빠져나옴. 자신의 크기나 상태가 달라졌기 때문에 바깥 반복문에서 다시 초기화
}

이 부분인데, 이 문제는 while문을 총 두개 써야한다. 그 중 안쪽 while문에 있는 if문이다.

자신보다 크기가 작으면 먹어치우고, 아기상어의 위치를 그 먹이로 업데이트 한 다음에 바로 빠져나온다.

 

이부분도 또 관건인데, 먹어치울때마다 아기상어의 크기가 달라지고, 위치가 달라지고, 또 그에 따라 먹을 수 있는 먹이가 달라지므로 방문 배열과 우선순위 큐를 다시 초기화한다.

 

그럼 여기서 의문인점: 그럼 우선순위 큐 맨 앞에꺼만 먹는 거 아닌가? 라고 생각들 수 있는데, 원래 우선인 먹이를 먹어야 된다고 문제에 써있기 때문에 굳이 우선순위가 낮은걸 먹을 필요가 없다. 그리고 언젠가 먹게 되어있다. 그래서 가장 우선으로 먹어야 하는 우선순위 큐 가장 맨 앞에 있는 것을 poll하고 먹은 다음, 바로 빠져나오면 된다.

 

  if (!flag) {
        break;
    }
    if (eat == size) {
        size++;
        eat = 0;
    }
 }

 

 

빠져 나온 다음에는 이 코드가 실행된다. 위에 flag =false로 해두고, 결국 먹이를 찾지 못했으면 코드를 끝낸다.

먹은 먹이와 사이즈가 같아지면 사이즈를 하나 늘리고, 먹은 먹이를 초기화한다.

그다음엔 다시 무한 반복문을 돈다.

    while (true) {
            PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
                if (o1[2] != o2[2]) {
                    return o1[2] - o2[2];
                } else if (o1[0] != o2[0]) {
                    return o1[0] - o2[0];
                }
                return o1[1] - o2[1];
            });

            visited = new boolean[N][N];
            pq.add(new int[]{r, c, 0});
            visited[r][c] = true;

여기서 다시 우선순위 큐를 초기화해주고, 방문배열을 초기화한다.

r,c 는 아기상어의 위치인데, 아까 먹은 먹이로 지정이 되어있을 거기 때문에 다시 아기상어의 위치를 넣어준다.

3. BFS로 먹이 찾는 과정 

 for (int i = 0; i < 4; i++) {
    int nx = current[0] + dx[i];
    int ny = current[1] + dy[i];
    if (isValid(nx, ny) && map[nx][ny] <= size && !visited[nx][ny]) {
        visited[nx][ny] = true;
        pq.add(new int[]{nx, ny, current[2] + 1});
    }
}

이부분은 일반적인 BFS와 같다. 방문하지 않았거나 && 범위를 넘지 않았거나 && 크기가 size보다 작거나 같은 아이들은 아기 상어가 지나갈 수 있고, 혹은 먹을 수 있으므로 큐에 넣어준다. 큐에 넣는 순간 자동으로 우선순위가 정해질 것...!

그리고 방문처리를 해준다.

 

이렇게 뜨문 뜨문 보면 이해 안 가는데 전체를 보면 이해할 수 있다..!

전체 코드 

package org.bj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 아기상어 {
    static int N, eat, time, r, c = 0;
    static boolean[][] visited;
    static int[][] map;
    static int size = 2;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                int num = Integer.parseInt(st.nextToken());
                if (num == 9) {
                    r = i;
                    c = j;
                    map[i][j] = 0;
                } else {
                    map[i][j] = num;
                }
            }
        }
        while (true) {
            PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
                if (o1[2] != o2[2]) {
                    return o1[2] - o2[2];
                } else if (o1[0] != o2[0]) {
                    return o1[0] - o2[0];
                }
                return o1[1] - o2[1];
            });

            visited = new boolean[N][N];
            pq.add(new int[]{r, c, 0});
            visited[r][c] = true;

            boolean flag = false;
            while (!pq.isEmpty()) {
                int[] current = pq.poll();
                int x = current[0];
                int y = current[1];
                int dir = current[2];
                if (map[x][y] > 0 && map[x][y] < size) { //자기보다 크기가 작으면
                    eat++; //먹어치우고
                    flag = true;
                    map[x][y] = 0;
                    time += dir; //이동시간 증가
                    r = x;
                    c = y; //아기상어 위치 업데이트
                    break; //첫번째 먹이를 먹으면, 빠져나옴. 자신의 크기나 상태가 달라졌기 때문에 바깥 반복문에서 다시 초기화
                }
                for (int i = 0; i < 4; i++) {
                    int nx = current[0] + dx[i];
                    int ny = current[1] + dy[i];
                    if (isValid(nx, ny) && map[nx][ny] <= size && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        pq.add(new int[]{nx, ny, current[2] + 1});
                    }
                }
            }
            if (!flag) {
                break;
            }
            if (eat == size) {
                size++;
                eat = 0;
            }
        }
        System.out.println(time);
    }

    private static boolean isValid(int x, int y) {
        return x >= 0 && y >= 0 && x < N && y < N;
    }
}

 

 

 

너무 어려웠다... 이게 골드 3이 맞는지 다시 한 번 문제 점검이 필요함

아오