BOJ. 16236번. 아기상어

 

이번엔 아기상어 문제다. 조건에서 '가까운 물고기를 먹는다'는 조건이 꽤나 까다로웠다.
먹을 수 있는 물고기들의 좌표를 모아서 sorting하는 간단한 방법이 있는데, 방향의 우선순위를 정해서 DFS적인 느낌으로 하려다 보니 풀이에 애를 먹었다. 그 외에 구현은 그렇게 어렵지 않다. 

1. 먹을 수 있는 물고기를 찾는다.
    - 상어가 다음 위치로 갈 수 있는 경우라면, 움직일 때마다 거리를 나타내는 배열에 값을 1씩 추가한다.
    - 만약에 움직인 위치가 0이 아니고, 먹을 수 있는 고기라면, 고기 후보군에 넣어준다.
    - 만약 마지막 후보군의 위치보다 거리배열의 위치가 크면, 더이상 진행하지 않는다.

2. 고기 후보군을 Sorting한다.

3. 가서 잡아먹고, 거리만큼 시간에 더해준다. -> 상어 위(잡아먹은 고기수)를 초기화 시켜준다.

www.acmicpc.net/problem/16236

16236번: 아기 상어

 

package week8;

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

public class Day4BOJ16236 {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	
	static int n,time,sy,sx,babysharkSize,babysharkTmp;
	static ArrayList<Fish> fishQ = new ArrayList<Fish>();
	static int[][] map,route;
	static int[] dy = {-1,0,1,0};
	static int[] dx = {0,-1,0,1};
 
	static class Fish implements Comparable<Fish>{
		int y,x,dist;
		public Fish(int y, int x, int dist) {
			this.y = y;
			this.x = x;
			this.dist = dist;
		}
		@Override
		public int compareTo(Fish o) {
			if(this.dist > o.dist) return 1;
			else if(this.dist == o.dist) {
				if(this.y > o.y) return 1;
				else if(this.y == o.y) {
					if(this.x > o.x) return 1;
					else return -1;
				}
				else return -1;
			}else return -1;
		}		
	}
	
	private static boolean checkBound(int y, int x) {
		return (y>=0 && y<n && x>=0 && x<n) ? true : false;
	}
	
	private static void searchFish() {
		Queue<Fish> tmpq = new LinkedList<Fish>();
		route = new int[n][n];
		tmpq.add(new Fish(sy,sx,0)); // 상어 초기위치;
		route[sy][sx]=1; // 방문표시
		
		while(!tmpq.isEmpty()) {
			Fish shark = tmpq.poll();
			int oy = shark.y;
			int ox = shark.x;
			if(fishQ.size() != 0 && route[oy][ox] > fishQ.get(fishQ.size() - 1).dist) { // 이러면 진행못함
				return;
			}
			for(int d=0; d<4; d++) {
				int ny = oy+dy[d];
				int nx = ox+dx[d];
				if(checkBound(ny,nx) && route[ny][nx]==0 && map[ny][nx] <= babysharkSize) {
					if(map[ny][nx] != 0 && map[ny][nx] < babysharkSize) {
						fishQ.add(new Fish(ny, nx, route[oy][ox]));
					}
					route[ny][nx] = route[oy][ox] + 1;
					tmpq.add(new Fish(ny,nx,0));
				}
			}
		}
	}
	
	private static void catchFish() {
		sy = fishQ.get(0).y;
		sx = fishQ.get(0).x;
		map[sy][sx] = 0; // 잡아먹음
		babysharkTmp++;  // 상어위에 한놈추가 
		time += fishQ.get(0).dist; // 그때까지 거리 더함
		fishQ.clear();
		if(babysharkTmp == babysharkSize) {
			babysharkSize++;
			babysharkTmp = 0;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		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) {
					sy = i; // 상어 초기 좌표 저장
					sx = j;
				}
			}
		}
		
		map[sy][sx]=0; // 좌표 초기화
		babysharkSize=2; // 사이즈 초기화
		
		while(true) {
			searchFish();
			if(fishQ.size()==0) break;
			Collections.sort(fishQ); // 먼저 잡아먹어야 하는놈
			catchFish();
		}
		
		System.out.println(time);
	}
	
}