[백준] 16236 아기 상어 - Implementation / Java

• 문제 링크

16236번: 아기 상어

 

• 풀이 과정

배열을 입력받을 때 상어의 위치와 거리의 초기값을 Shark 객체에 저장하고

bfs 탐색을 할 함수에 상어의 크기(2), 먹은 물고기 수 (0), 거리(0) 를 매개변수로 전달한다.

 

bfs 탐색을 하되 문제에 제시된 조건을 적용하기 위해선 우선 순위 큐를 활용해야한다.

상어와의 거리, y축, x축 순으로 PriorityQueue 자료구조에 Comparator 오름차순으로 비교하여 우선 순위를 지정한다.

 

이러한 규칙을 전제로 상어가 이동할 위치를 큐에 삽입하며,

배열의 범위 내이고, 이동할 위치가 상어의 크기보다 같거나 작을 시 이동하고

이동한 위치에 먹이가 존재하고 상어의 크기보다 작을 시 그에 따른 값들의 변화를 준다.

 

상어가 먹은 물고기의 수와 상어의 크기가 같을 시 상어의 크기를 1 증가시키고,

더 이상 먹을 물고기가 없을 경우 지금까지 증가된 소요된 시간을 반환해 정답을 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static int n;
	static int[][] map;
	static int[] dy = { -1, 1, 0, 0 };
	static int[] dx = { 0, 0, -1, 1 };
	static Shark now;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		n = Integer.parseInt(br.readLine());
		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) {
					now = new Shark(i, j, 0);
					map[i][j] = 0;
				}
			}
		}

		bw.write(bfs(2, 0, 0) + "\n");
		bw.flush();
	}

	private static int bfs(int size, int eat, int cnt) {
		while (true) {
			PriorityQueue<Shark> q = new PriorityQueue<>(
					(o1, o2) -> o1.dist != o2.dist ? Integer.compare(o1.dist, o2.dist)
							: (o1.y != o2.y ? Integer.compare(o1.y, o2.y) : Integer.compare(o1.x, o2.x)));
			q.offer(new Shark(now.y, now.x, 0));

			boolean[][] visit = new boolean[n][n];
			visit[now.y][now.x] = true;

			boolean flag = false;
			while (!q.isEmpty()) {
				now = q.poll();

				if (map[now.y][now.x] != 0 && map[now.y][now.x] < size) {
					map[now.y][now.x] = 0;
					eat++;
					cnt += now.dist;
					flag = true;
					break;
				}

				for (int i = 0; i < 4; i++) {
					int ny = now.y + dy[i];
					int nx = now.x + dx[i];

					if (ny < 0 || nx < 0 || ny >= n || nx >= n || map[ny][nx] > size || visit[ny][nx])
						continue;

					q.offer(new Shark(ny, nx, now.dist + 1));
					visit[ny][nx] = true;
				}
			}

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

		return cnt;
	}

	private static class Shark {
		int y;
		int x;
		int dist;

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

}