[백준] 16235 아기상어

문제보기

1. 일단 먹을 수 있는 물고기 중 가장 가까운것을 찾아야함 ( 거리는 BFS 로 구함 )
2. 아기상어의 위치를 옮겨주고, 그 물고기를 먹고(먹은 갯수+1), 물고기를 삭제한다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

// 물고기의 좌표와 크기를 담는다
class Fish{
	int x;
	int y;
	int size;
	Fish(int x, int y, int size){
		this.x = x;
		this.y = y;
		this.size = size;
	}
}
// BFS를 위해 필요한 클래스
class Pair{
	int x;
	int y;
	Pair(int x, int y){
		this.x = x;
		this.y = y;
	}
}

public class Main {
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	static int n;
	static Fish baby;
	static List<Fish> list;
	static int[][] check;
	static int[][] map;
	static int dist;
	
  // 남은 모든 물고기가 다 크거나 같다면 참을 반환
	static boolean allBigger() {
		int size = baby.size;
		for(int i = 0 ; i < list.size() ; i++) {
			if(size > list.get(i).size) {
				return false;
			}
		}
		return true;
	}
  // 물고기까지 가는 거리를 계산 
	static int reachable(int idx) {
		Queue<Pair> q = new LinkedList<>();
		q.add(new Pair(baby.x, baby.y));
		check[baby.x][baby.y] = 0; // 0에서 출발
		int gx = list.get(idx).x; // 목표지점의 행
		int gy = list.get(idx).y; // 목표지점의 열 
		
		while(!q.isEmpty()) {
			Pair p = q.remove();
			int x = p.x;
			int y = p.y;
			if( x == gx && y == gy) { // 도달했다면 
				return dist = check[x][y]; // 반환
			}
			
			for(int k = 0 ; k < 4 ; k++) { // 네 방향으로 갈 수 있다
				int nx = x + dx[k];
				int ny = y + dy[k];
				// 맵에 존재하는지, 방문한적이 없는지
				if(nx >= 0 && nx < n && ny >= 0 && ny < n && check[nx][ny] == -1) {
					if(baby.size >= map[nx][ny]) { // 지나갈 수 있는지
						check[nx][ny] = check[x][y] + 1;
						q.add(new Pair(nx, ny));
					}
				}
			}
		}
		// 도착하지 못했다면 최대거리 반환(20x20짜리 맵이 최대라서 대충 500보단 늘 거리가 작다)
		return 500;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		list = new ArrayList<Fish>();
		baby = new Fish(-1, -1, 2);
		map = new int[n][n];
		
		for(int i = 0 ; i < n ; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j = 0 ; j < n ; j++) {
				int size = Integer.parseInt(st.nextToken());
				if(size == 0) {
					continue;
				}else if(size == 9) {
					baby.x = i; baby.y = j;
				}else {
					list.add(new Fish(i, j, size));
					map[i][j] = size;
				}
			}
		}
		
		int time = 0; 
		int eaten = 0; // 사이즈업 직후부터 먹은 물고기 수 저장 
		
		while(true) {
      // 더이상 물고기가 없거나 아기상어보다 큰 물고기만 남았다면..
			if(list.size() == 0 || allBigger()) {
				break;
			}
			
			int x = baby.x;
			int y = baby.y;
			int size = baby.size;
			int min = 500; // 먹이까지의 거리
			int fx = -1; // 먹이의 행
			int fy = -1; // 먹이의 열
			int idx = -1; // 먹이의 인덱스
			
			for(int i = 0 ; i < list.size() ; i++ ) {
				if(list.get(i).size < size) { // 먹이는 아기상어보다 작아야 함
					check = new int[n][n]; // check 배열 초기화
					for(int row = 0 ; row < n ; row++) {
						Arrays.fill(check[row], -1);
					}
					
					int dist = reachable(i); // 먹이까지의 거리 산출
					if(dist < min) { // 최소 거리 갱신
						min = dist;
						fx = list.get(i).x;
						fy = list.get(i).y;
						idx = i;
					}
				}
			}
			
      // 최소거리 갱신에 실패했다 -> 먹을 물고기는 있지만 갈 수가 없다 -> 종료
			if(min == 500) break;
			
			time += min; // 걸린 시간 = 거리*1 이므로
			baby.x = fx; // 아기상어의 위치를 옮겨준다
			baby.y = fy;
			eaten++; // 먹는다 
			if(eaten == size) { // 사이즈 업 조건
				baby.size++;
				eaten = 0;
			}
      // 먹이의 흔적을 지운다
			list.remove(idx);
			map[fx][fy] = 0;

		}
		
		System.out.println(time);
		
	}
}