[백준] 16236. 아기상어 (Java)

아기상어 크기 설정시 주의! (무한루프에 빠질 수 있음)

16236번: 아기 상어

풀이

문제 자체는 어렵지 않으나 반례를 잘 생각해야 한다. (문제 푼 시간보다 디버깅 시간이 더 오래걸렸다..)

테스트 케이스는 다 맞는데 2%에서 틀리길래 뭔가 했더니 아기상어 크기가 9보다 커질 수 있다는 사실을 생각 못하고 있었다..

 

그리고 사소한 실수지만 만약 y, x가 아니라 x, y로 받았을 경우 위쪽은 y가 아니라 x이다.

 

 

 

• BABY_SHARK: 현재 아기상어 위치값. N 범위는 최대 20이므로 500으로 설정했다.
• int[][] sea: 물고기와 아기상어 위치 및 크기 정보
• babyShark: 현재 아기상어의 크기
• eaten: 아기상어가 먹은 물고기 수
• babySharkX, babySharkY: 현재 아기상어 좌표값
• boolean flag: 아기상어가 더이상 먹을 물고기가 없는 경우를 알려준다.
• static class Shark: x, y 좌표 + 이동거리를 저장하기 위해 만든 class

 

Logic

1. 처음에 입력받을 때 아기상어 위치를 저장하고 flag=true일 때 까지 while 반복문을 수행한다.
2. 아기상어 위치에 대해 큐를 두 개 사용하는데,

• q: 일반적인 BFS 탐색용
• pq: 문제에서 제시한 조건에 맞는 물고기를 우선순위에 따라 넣음
  1. ① 범위를 벗어나거나 ② 물고기가 아기상어보다 크거나 ③ 이미 지나온 곳이라면 탐색하지 않는다.
  2. ① 물고기가 아기상어보다 작은데 ② 해당 위치가 0이 아닌경우 먹을 수 있으므로 pq에 넣는다.
  3. 다음 탐색할 위치인 q에 넣는다.

3. q가 비었다면 아기상어가 갈 수 있는 모든 위치를 갔다는 의미이다.
   • 만약 pq가 비었다면 먹을 물고기가 없으므로 flag = true로 값을 바꿔준다.
   • 먹을 물고기들이 있다면 eaten변수를 증가시킨다.
   • 만약 아기상어 크기와 같아진다면 아기상어크기 += 1을 하고 eaten 변수는 초기화시킨다.
     아기상어 좌표를 먹은 물고기 좌표로 치환하고, 아기상어의 예전 위치는 -1, 현재 위치는 BABY_SHARK로 업데이트한다.

 

코드

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

public class Main {
    static final int BABY_SHARK = 500;
    static int[][] sea;
    static int N, t, babySharkX, babySharkY, babyShark = 2, eaten;
    static boolean flag = false;
    static int[] pos_x = { 1, 0, -1, 0 };
    static int[] pos_y = { 0, 1, 0, -1 };

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();
        while (!flag) {
            solve();
        }
        bw.write(String.valueOf(t));
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        sea = new int[N + 2][N + 2];

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                sea[i][j] = Integer.parseInt(st.nextToken());
                if (sea[i][j] == 9) {
                    babySharkX = i;
                    babySharkY = j;
                }
            }
        }
        br.close();
    }

    public static void solve() {
        boolean[][] visited = new boolean[N + 2][N + 2];
        Queue<Shark> q = new LinkedList<>();
        PriorityQueue<Shark> pq = new PriorityQueue<>(new Comparator<Shark>() {

            @Override
            public int compare(Shark o1, Shark o2) {
                if (o1.d == o2.d) {
                    if (o1.x == o2.x)
                        return Integer.compare(o1.y, o2.y);
                    return Integer.compare(o1.x, o2.x);
                }
                return Integer.compare(o1.d, o2.d);
            }

        });

        q.offer(new Shark(babySharkX, babySharkY));
        while(!q.isEmpty()) {
            int x = q.peek().x;
            int y = q.peek().y;
            int d = q.peek().d;
            q.poll();

            for (int dir = 0; dir < 4; dir++) {
                int x_next = x + pos_x[dir];
                int y_next = y + pos_y[dir];

                if (x_next < 1 || x_next > N || y_next < 1 || y_next > N) continue;
                if (babyShark < sea[x_next][y_next] || visited[x_next][y_next]) continue;

                if (babyShark > sea[x_next][y_next] && sea[x_next][y_next] > 0)
                    pq.offer(new Shark(x_next, y_next, d + 1));
                else
                    q.offer(new Shark(x_next, y_next, d + 1));

                visited[x_next][y_next] = true;
            }
        }

        if (pq.isEmpty()) flag = true;
        else {
            eaten++;
            t += pq.peek().d;

            if (babyShark == eaten) {
                babyShark++;
                eaten = 0;
            }

            sea[babySharkX][babySharkY] = -1;
            babySharkX = pq.peek().x;
            babySharkY = pq.peek().y;
            sea[babySharkX][babySharkY] = BABY_SHARK;
        }
    }

    static class Shark {
        int x;
        int y;
        int d;

        public Shark(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }

        public Shark(int x, int y) {
            this(x, y, 0);
        }

    }
}

 

실행결과