[backjoon]16236 아기상어 java

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

중간 중간의 목적지를 분명하게 정하는 것이 중요한 문제!

1. 아기 상어의 위치에서 최단 거리 내 갈 수 있는 모든 물고기 위치의 경우의 수를 구한다.

2. 물고기가 두 마리 이상이라면 기준에 맞게 정렬한다.

3. 중간 중간 상어를 관리해주기 위해 자료형 shark를 만들었다.

 

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

class Main {
	static int N;
	static int[][] map, time;
	static shark baby;
	static Dot start;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		map = new int[N][N];
		baby = new shark();
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int cur = Integer.parseInt(st.nextToken());
				if (cur == 9) {
					cur = 0;
					start = new Dot(i, j);
				}
				map[i][j] = cur;
			}
		}
		
		// 먹을 수 있는 모든 경우의 수를 구해서 정렬 후 계속 해서 탐색해야함.
		while (true) {

			// 1. 먹을 수 있는 물고기 경우의 수 구하기
			ArrayList<Dot> list = search();
			if (list.size() == 0) break;
			
			// 2. 물고기를 기준에 맞게 정렬
			Dot[] sort = new Dot[list.size()];
			for (int i = 0; i < list.size(); i++) {
				sort[i] = list.get(i);
			}
			Arrays.sort(sort);

			// 3. 가장 조건에 부합하는 물고기를 먹고 먹은 갯수에 맞게 나이 조절.
			Dot cur = sort[0];
			map[cur.row][cur.col] = 0;
			start = new Dot(cur.row, cur.col);
			baby.cnt++;
			if (baby.cnt == baby.size) {
				baby.cnt = 0;
				baby.size++;
			}

			// 4. 한 마리 먹을 때 마다 1초 증가
			baby.sec += time[cur.row][cur.col];
		}
		System.out.println(baby.sec);
	}

	public static ArrayList<Dot> search() {
		ArrayList<Dot> list = new ArrayList<>();
		Queue<Dot> queue = new LinkedList<>();
		queue.add(start);
		boolean[][] marked = new boolean[N][N];
		int[][] dirs = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
		time = new int[N][N];
		int minTime = Integer.MAX_VALUE;
		while (!queue.isEmpty()) {
			Dot cur = queue.poll();

			for (int i = 0; i < 4; i++) {
				int nextR = cur.row + dirs[i][0];
				int nextC = cur.col + dirs[i][1];

				if (nextR < 0 || nextC < 0 || nextR >= N || nextC >= N) continue;
				if (marked[nextR][nextC]) 	continue;
				int size = map[nextR][nextC];
				if (size > baby.size) continue;
				
				marked[nextR][nextC] = true;
				time[nextR][nextC] = time[cur.row][cur.col] + 1;
				
                //* 최단 거리를 조건을 위해 꼭 minTime을 설정해줘야함.
				if (size != 0 && size < baby.size) {
					int sec = time[nextR][nextC];
					if (sec > minTime) continue;
					minTime = time[nextR][nextC];
					list.add(new Dot(nextR, nextC));
				} else {
					queue.add(new Dot(nextR, nextC));
				}
			}
		}
		return list;
	}
}

class Dot implements Comparable<Dot> {
	int row;
	int col;

	Dot(int r, int c) {
		this.row = r;
		this.col = c;
	}

	@Override
	public int compareTo(Dot o) {
		if (this.row == o.row)
			return this.col - o.col;
		return this.row - o.row;
	}
}

class shark {
	int size = 2;
	int cnt = 0;
	int sec;
}