[백준 16236] 아기 상어 - JAVA

문제 링크 : https://www.acmicpc.net/problem/16236

코테 스터디에서 풀었던 내용입니다.
스터디 할 때는 PPT를 열심히 작성해서 발표했기 떄문에
스터디 때 풀었던 문제들에 대해서는 그림 자료를 사용합니다!

---

문제 정의

문제의 조건이 많기 때문에 분리해서 설명하겠습니다.

아기상어의 행동 패턴

1. 자기 자신보다 작은 물고기 한마리를 탐색
   1-1. 작은 물고기가 있는 경우 2번으로 이동
   1-2. 작은 물고기가 없는 경우 종료
2. 탐색 후 해당 물고기를 먹기 위해 이동
3. 먹은 후 성장
4. 1번부터 반복

---

이동 관련 로직

간단하게 말해

• 자기보다 작은 물고기가 있는 좌표로는 이동 가능, 먹는 것도 가능
• 자기와 같은 크기의 물고기가 있는 좌표로는 이동만 가능
• 자기보다 큰 물고기가 있는 좌표로는 이동도 안됨

예시로 오른쪽 그림과 같이 물고기와 상어가 존재할 때
아기 상어는 크기 3인 물고기가 있는 좌표를 제외하고는 모두 이동 가능합니다.

---

성장 관련 로직

상어는 자기 자신의 크기만큼 물고기를 먹어야 크기가 1 성장합니다.

• 성장하는 건 마리 수 으로 결정

---

탐색 관련 로직

기본적으로 아기 상어는 먹을 수 있는 물고기 중 가장 가까운 물고기를 먹습니다.

그럼 가장 가까운 물고기가 여러마리라면?

가장 가까운 물고기가 여러 마리인 경우 로직은 다음과 같습니다.
1. 가장 위에 있는 물고기
2. 가장 왼쪽에 있는 물고기

가장 위에 있는 물고기를 먼저 먹으며
같은 y좌표에 존재하는 물고기들 중에서는

가장 왼쪽에 있는 물고기,
즉, x좌표가 작은 물고기부터 먹게 됩니다.

---

접근 방법

로직은 다음과 같습니다.

1. 현재 그리드 내에 먹을 수 있는 물고기가 있는지 canEat() 메서드로 탐색
   1-1. 먹을 수 있다면 2번으로 이동
   1-2. 먹을 수 없다면 현재까지의 총 이동 거리를 출력 후 종료
2. bfs()를 수행하며 이 때 이동 거리를 총 이동 거리에 누적
3. 성장 로직인 eat()을 수행 후 다시 1을 반복

초기화

대부분은 주석에 담겨 있지만
prey라는 배열에 대해서는 생소할 수 있기에 설명드리겠습니다.

---

최적화를 위한 prey 배열

현재 그리드 내에 먹을 수 있는지 탐색하기 위해서
기본적으로 생각할 수 있는게
그리드 내를 전체 순회하면서 먹을 수 있는 물고기를 찾는 것입니다.

이렇게 하면 매 번 물고기를 찾을 때마다 $O(N^2)$의 시간 복잡도가 소요됩니다.

시간복잡도를 최적화 하기 위해
먹이의 크기와 마리 수를 저장하는 prey 배열을 선언했습니다.

그래서 이 배열은 어떻게 활용하는데?

1. 초기화 단계에서 현재 그리드(공간) 내에 존재하는 물고기들을 탐색합니다.
2. 먹이의 크기에 따라 prey 배열에 접근해 값을 1 증가시킵니다.
   2-1. prey[i]의 의미는 크기가 i인 물고기의 수를 의미합니다.
   2-2. 그리드 내 크기가 3인 물고기가 2마리 있다면 prey[3]의 값은 2로 초기화됩니다.

이렇게 처음에 모든 물고기의 크기와 마리 수를 스캔해 저장해놓고 현재 물고기의 크기와 비교하면 $O(1)$만에 먹을 수 있는 물고기가 있는지 스캔 가능합니다.

---

canEat() 메서드

static boolean canEat() {
	for (int i = 1; i < Math.min(size, 7); i++) {
		if (prey[i] > 0) return true;
	}
	return false;
}

그래서 canEat()의 로직은 간단합니다.

• 상어의 크기 size 보다 작은 물고기를 찾기 위해 prey 배열 탐색
• 작은 물고기가 있으면 true 반환
• 없으면 false 반환

---

bfs() 메서드

// 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
static int bfs() {
	ArrayDeque<BabyShark> queue = new ArrayDeque<>();
	queue.offer(new BabyShark(x, y, 0));
	boolean[][] visited = new boolean[N][N];
	visited[y][x] = true;

	while (!queue.isEmpty()) {
		BabyShark shark = queue.poll();
		x = shark.x;
		y = shark.y;
		int dist = shark.dist;

		if (space[y][x] != 0 && size > space[y][x]) {
			while (!queue.isEmpty()) {
				BabyShark candidate = queue.poll();

				if (candidate.dist > dist) break;
				int cx = candidate.x;
				int cy = candidate.y;

				if (space[cy][cx] != 0 && size > space[cy][cx]) {
					if (cy < y || (cy == y && cx < x)) {
						y = cy;
						x = cx;
					}
				}
			}
			prey[space[y][x]]--;
			space[y][x] = 0;
			return dist;
		}

		// 4방향 갱신
		for (int d = 0; d < 4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];

			// 자신의 크기보다 큰 상어가 있는 경우 가지 못한다.
			if (0 <= ny && ny < N && 0 <= nx && nx < N && !visited[ny][nx] && space[ny][nx] <= size) {
				visited[ny][nx] = true;
				queue.offer(new BabyShark(nx, ny, dist + 1));
			}
		}
	}
	return -1;
}

기본 bfs()와 대부분의 로직은 동일하지만
다른 부분이 존재합니다.

그 부분을 찾기 위해선 시뮬레이션을 해보겠습니다.

1. 초기 시작 위치 저장

queue.offer(new BabyShark(x, y, 0));

아기 상어의 초기 위치와 이동거리를 저장하고 bfs를 수행합니다.

2. bfs 수행

아기 상어가 bfs를 수행하면서
거리가 1인 위치에 먹을 수 있는 물고기가 있는지
거리가 2인 위치에 먹을 수 있는 물고기가 있는지
거리가 3인 위치에 먹을 수 있는 물고기가 있는지..
순차적으로 진행할겁니다.

그러다가! 아기 상어가 현재위치에 먹을 수 있는 물고기가 존재한다면?

다음을 체크해야합니다.

• 같은 거리에 또 먹을 수 있는 물고기가 존재하는가?

if (space[y][x] != 0 && size > space[y][x])

이 코드로 탐색을 한 후

다음 로직을 수행합니다.

while (!queue.isEmpty()) {
    BabyShark candidate = queue.poll();

    // BFS로 찾은 최단 거리보다 멀어지면 탐색 중단
    if (candidate.dist > dist) break;
    
    int cx = candidate.x;
    int cy = candidate.y;

    // 먹을 수 있는 물고기인지 확인 (빈 칸이 아니고, 상어보다 크기가 작은 경우)
    if (space[cy][cx] != 0 && size > space[cy][cx]) {
       // 문제의 우선순위 적용: 1. 가장 위쪽(y) / 2. 가장 왼쪽(x)
       if (cy < y || (cy == y && cx < x)) {
          y = cy;
          x = cx;
       }
    }
}

// 최종 결정된 먹이 처리
prey[space[y][x]]--; // 전체 물고기 수 업데이트
space[y][x] = 0;      // 지도에서 물고기 제거
return dist;         // 이동 거리 반환

이미 같은 거리에 이동할 수 있는 좌표들이
bfs로직에 의해 quque 안에 저장되어 있습니다.

이 좌표들을 모두 꺼내서 다음과 같은 로직을 수행합니다.

• 먹을 수 있는가?
• 먹을 수 있다면 이동 로직에 의해 더 위쪽, 더 왼쪽에 존재하는 먹이를 먹기 위해 좌표를 변경해라

queue 안의 모든 값들을 꺼내 비교했다면
이동 조건에 의해 선택된 좌표을 현재 아기 상어의 좌표로 설정하고
이동 거리를 반환합니다.

---

eat() 로직

static void eat() {
    count++;
    if (count == size) {
        size++;
        count = 0;
    }
}

섭취 로직은 단순합니다.

호출 될 때마다
먹기 때문에 먹은 횟수(count)를 증가시키고
내 크기만큼 물고기를 먹었다면
사이즈를 1 증가시키고 count를 초기화합니다.

---

예제

입력

4
4 3 2 1
0 0 0 0
0 0 9 0
1 2 3 4

입력은 다음과 같고 그림으로 표현하면 다음과 같습니다.

---

로직 수행

1. canEat()으로 먹을 수 있는 물고기를 탐색
   1-1. 아직 존재하기 때문에 true 반환

---

2. bfs 로직에 의해 같은 거리에 두 마리의 물고기가 존재하는 것을 파악

---

3. 해당 물고기가 있는 곳으로 이동 후 total_dist 증가, 해당 크기의 먹이 수 감소
4.eat() 로직 수행 count 증가

---

1. canEat()으로 먹을 수 있는 물고기를 탐색
   1-1. 아직 존재하기 때문에 true 반환

---

2. 한마리를 향해 이동
   2-1. 이동 거리 증가, 해당 크기의 먹이 수 감소

---

3. 먹은 횟수가 상어의 크기와 같으므로 사이즈 증가

---

1. canEat()으로 먹을 수 있는 물고기를 탐색
   1-1. 아직 존재하기 때문에 true 반환

---

2. 가장 가까운 물고기 선택
3. 이동해서 먹은 후 이동 거리와 횟수 증가, 해당 크기의 먹이 수 감소

---

1. canEat()으로 먹을 수 있는 물고기를 탐색
   1-1. 아직 존재하기 때문에 true 반환

---

2. 먹을 수 있는 물고기 선택
3. 이동해서 먹은 후 이동 거리와 횟수 증가, 해당 크기의 먹이 수 감소

---

1. canEat()으로 먹을 수 있는 물고기를 탐색
   1-1. 먹을 수 있는 물고기가 없으므로 false 반환
   1-2. total_dist 출력

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.StringTokenizer;


class BabyShark {
    int x, y, dist;
    public BabyShark(int x, int y, int dist) {
        this.x = x;
        this.y = y;
        this.dist = dist;
    }
}

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int[][] space;
    static int y;
    static int x;
    static int N;
    static int[] dy = {-1, 0, 0, 1};
    static int[] dx = {0, -1, 1, 0};
    static int[] prey = new int[7];
    static int size = 2;
    static int count = 0;
    static int total_dist = 0;

    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        space = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                space[i][j] = Integer.parseInt(st.nextToken());

                // 아기 상어 좌표
                if (space[i][j] != 0) {
                    if (space[i][j] == 9) {
                        y = i;
                        x = j;
                    }
                    else {
                        prey[space[i][j]]++;
                    }
                }
            }
        }

        space[y][x] = 0;
        while (canEat()) {
            int move = bfs();
            if (move == -1) break;
            total_dist += move;
            eat();
        }
        System.out.println(total_dist);
    }

    // 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
    static boolean canEat() {
        for (int i = 1; i < Math.min(size, 7); i++) {
            if (prey[i] > 0) return true;
        }
        return false;
    }

    // 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
    static int bfs() {
        ArrayDeque<BabyShark> queue = new ArrayDeque<>();
        queue.offer(new BabyShark(x, y, 0));
        boolean[][] visited = new boolean[N][N];
        visited[y][x] = true;

        while (!queue.isEmpty()) {
            BabyShark shark = queue.poll();
            x = shark.x;
            y = shark.y;
            int dist = shark.dist;

            if (space[y][x] != 0 && size > space[y][x]) {
                while (!queue.isEmpty()) {
                    BabyShark candidate = queue.poll();

                    if (candidate.dist > dist) break;
                    int cx = candidate.x;
                    int cy = candidate.y;

                    if (space[cy][cx] != 0 && size > space[cy][cx]) {
                        if (cy < y || (cy == y && cx < x)) {
                            y = cy;
                            x = cx;
                        }
                    }
                }
                prey[space[y][x]]--;
                space[y][x] = 0;
                return dist;
            }

            // 4방향 갱신
            for (int d = 0; d < 4; d++) {
                int ny = y + dy[d];
                int nx = x + dx[d];

                // 자신의 크기보다 큰 상어가 있는 경우 가지 못한다.
                if (0 <= ny && ny < N && 0 <= nx && nx < N && !visited[ny][nx] && space[ny][nx] <= size) {
                    visited[ny][nx] = true;
                    queue.offer(new BabyShark(nx, ny, dist + 1));
                }
            }
        }
        return -1;
    }


    static void eat() {
        count++;
        if (count == size) {
            size++;
            count = 0;
        }
    }
}