백준 - 16236번 아기상어

이 문제는 여러 조건들을 만족시키는 메소드를 기능 별로 분리해 만들어야 헷갈리지 않는다.

 

이 문제의 핵심은  "거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다." 를 어떻게 처리하느냐다.

 

나는 기능 별로 두가지 메소드로 나누었다.

1. bfs 메소드 : 다음에 먹을 가장 적절한 물고기의 위치와 거기로 가는데 걸린 시간 반환

2. move 메소드 : bfs 메소드를 호출해서 물고기를 먹고 time을 업데이트하는 재귀함수

 

나는 핵심 조건을 bfs 메소드에서 PriorityQueue를 이용해 처리했다.

PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
    @Override
    public int compare(int[] a, int[] b) {
        //시간이 같을 때
        if(Integer.compare(a[0],b[0])==0) {
            //x좌표 같을 때
            if(Integer.compare(a[1],b[1])==0) {
                //y좌표 같을 때
                return Integer.compare(a[2],b[2]);
            }
            return Integer.compare(a[1],b[1]);
        }
        return Integer.compare(a[0],b[0]);
    }
});

시간이 같을 때는 x좌표(map에서 위아래)를 비교하고 x좌표가 같을 때는 y좌표를 비교해서 정렬하도록 했다.

 

또 하나 유의할 점이, 아기 상어가 자기 자신을 먹을 수는 없기 때문에 크기가 9인 곳은 안 먹는다는 설정을 해야한다.

if(map[cur_i][cur_j]>0 && map[cur_i][cur_j] < size && map[cur_i][cur_j] != 9) {
    //먹을 수 있음
    return data;
}

 

다음은 코드 전문이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	static int[] xmove = {-1,0,0,1};
	static int[] ymove = {0,-1,1,0};
	
	public static int move(int size, int howManyEat, int[][] map) {
		int time = 0;
		
		int x = -1;  //상어 위치 x
		int y = -1;  //상어 위치 y
	
		for(int i=0; i<map.length; i++) {
	    	 for(int j=0; j<map.length; j++) {
	    		 if(map[i][j] == 9) {
	    			 x = i;
	    			 y = j;
	    		 }
	    	 }
		}
		
		int[] list = bfs(map, size);
		
		//먹을 수 있는 물고기가 없으면 끝
		if(list[0] == -1 || list[1] == -1 || list[2] == -1) {
			//먹을 수 없음
			return time;
		}else {
			//먹을 수 있음
			howManyEat = howManyEat+1;
			
			time += list[0];
			if(size == howManyEat) {
				size++;
				howManyEat = 0;
			}
			//System.out.println("먹으려는 애 좌표:"+list[1]+","+list[2]);
			map[x][y] = 0;
			map[list[1]][list[2]] = 9;
			time += move(size, howManyEat, map);
		}
		return time;
	}
	
	//다음에 먹을 먹이 위치와 걸린 시간 반환
	public static int[] bfs(int[][] map, int size) {
		int[] ans = new int[3];
		
		//초기화
		ans[0] = -1;
		ans[1] = -1;
		ans[2] = -1;
		
		int x = -1;  //상어 위치 x
		int y = -1;  //상어 위치 y
		
		int[][] graph = new int[map.length][map[0].length];  //몇칸 이동했는지 표시하는 배열
		
		loop:
		for(int i=0; i<map.length; i++) {
	    	 for(int j=0; j<map.length; j++) {
	    		 if(map[i][j] == 9) {
	    			 x = i;
	    			 y = j;
	    			 break loop;
	    		 }
	    	 }
		}
		
		PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
			@Override
			public int compare(int[] a, int[] b) {
				//시간이 같을 때
				if(Integer.compare(a[0],b[0])==0) {
					//x좌표 같을 때
					if(Integer.compare(a[1],b[1])==0) {
						//y좌표 같을 때
						return Integer.compare(a[2],b[2]);
					}
					return Integer.compare(a[1],b[1]);
				}
				return Integer.compare(a[0],b[0]);
			}
		});
		
		queue.offer(new int[] {0, x, y});
		
		while(!queue.isEmpty()) {
			int[] data = queue.poll();
			int cur_i = data[1];
			int cur_j = data[2];
			
			if(map[cur_i][cur_j]>0 && map[cur_i][cur_j] < size && map[cur_i][cur_j] != 9) {
				//먹을 수 있음
				return data;
			}
			
			for(int i=0; i<4; i++) {
				int next_i = cur_i + xmove[i];
				int next_j = cur_j + ymove[i];
				
				if(next_i<0 || next_i>=map.length || next_j<0 || next_j>=map[0].length || map[next_i][next_j] > size || graph[next_i][next_j] != 0) {
					continue;
				}
				
				//이동 가능
				graph[next_i][next_j] = graph[cur_i][cur_j] + 1;
				queue.offer(new int[] {graph[next_i][next_j], next_i, next_j});
			}
		}
		return ans;
	}

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

	     int n = Integer.parseInt(st.nextToken());
	     
	     int[][] map = new int[n][n];
	     
	     int size = 2;  //아기상어 크기
	     
	     int howManyEat = 0;  //먹은 먹이 개수
	     
	     for(int i=0; i<n; i++) {
	    	 st = new StringTokenizer(br.readLine());
	    	 for(int j=0; j<n; j++) {
	    		 int k = Integer.parseInt(st.nextToken());
	    		 map[i][j] = k;
	    	 }
	     }
	     
	     System.out.println(move(size, howManyEat, map));
	    
	}

}

 

테스트 케이스는 다음을 참고하자.

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

14


//위쪽,왼쪽이 우선순위가 높게 하기
6
5 4 3 2 3 4
4 3 2 3 4 5
3 2 9 5 6 6
2 1 2 3 4 5
3 2 1 6 5 4
6 6 6 6 6 6

60



//내가 나를 먹으면 안 됨
7
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 9

48