백준 16236번: 아기 상어

문제 설명

• 상어는 자신보다 크기가 작은 물고기만 잡아먹을 수 있습니다.
• 상어는 자신보다 크기가 큰 물고기칸을 지나갈 수 없습니다.
• 상어는 자신의 크기만큼 물고기를 먹으면 크기가 증가합니다.
• 동일한 거리의 먹이가 여러개 있다면 더 위에, 더 왼쪽에 있는 먹이를 선택합니다.
  • 현재에서 거리가 같은 먹이가 3개 있다면 셋 중 하나만 선택합니다.
    • 3개 다 먹는다 X
    • 거리 우선순위가 가장 큰 하나만 먹고, 달라진 좌표에서 다시 가까운 먹이를 찾는다 O

접근법

• 거리가 가까운 먹이를 찾아야 하기 때문에 BFS를 사용했습니다.
• 거리가 같은 후보들을 찾기 위해 2중 while문을 활용했습니다.
• 상어 객체를 생성해 좌표, 상어의 크기, 먹은 횟수를 관리했습니다.
  

틀린 부분

• 물고기와 상어의 거리를 맨하탄 거리로 계산했었습니다.
  • 상어는 지나가지 못하는 공간이 존재하기 때문에 단순히 좌표차이로 거리를 구하면 안되고 BFS의 실행횟수만큼을 거리로 구해야 합니다.
• 상어의 위치를 초기화하지 않았습니다.
  • 최초 상어의 위치를 나타내는 값(9)은 크기가 9인 물고기가 아닙니다.
    • 해당 칸은 잡아먹을수 없으며, 항상 지나갈 수 있어야 합니다.
  • 상어정보를 저장한 뒤 0으로 초기화 해줘야 합니다.

정답

import java.util.*;

public class Main {
	static int[] dx = {1,0,-1,0};
	static int[] dy = {0,1,0,-1};
	static int N;
	static int move_cnt = 0; // 총 움직인 횟수(최종 정답)
	static int[][] board;
	static Baby shark;
	public static void main(String[] args) {
		// 입력값 받기
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		board = new int[N][N];
		for (int i = 0; i < board.length; i++) {
			for (int j = 0; j < board.length; j++) {
				board[i][j] = sc.nextInt();
				if(board[i][j] == 9) {
					shark = new Baby(i,j,2,0); // 상어 객체 생성
					board[i][j] = 0; // 9는 상어의 시작 위치일뿐 못지나가는 길이 아니기 때문에 0으로 바꿔줘야함
				}
			}
		}
		
		// 상어가 밥을 못먹을때까지 BFS실행
		while(true) {
			if(!BFS(shark.x,shark.y,shark)) {
				break;
			}
		}
		System.out.println(move_cnt);
	}
	
	
	public static boolean BFS(int x, int y, Baby shark) { // BFS가 boolean을 반환해서 먹을 수 있는 후보가 존재하는지 판단
    	// BFS에 필요한 기본 세팅
		boolean[][] v= new boolean[N][N];
		v[x][y] = true;
		Queue<int[]> q = new LinkedList<int[]>();
		int[] axis = {x,y};
		q.add(axis);
        
		List<int[]> eat_lst = new ArrayList<int[]>(); // 깊이가 같은 형제들을 담기 위한 리스트
		int cnt = 0; // DFS의 깊이 == 먹이를 찾기까지 상어가 이동한 횟수
        
		while(!q.isEmpty()) {
			int size = q.size();
			cnt++;
			while(--size>=0) { // depth별로 끊어서 진행 -> 거리가 같은 먹이를 하나의 리스트에 담음
				int[] val = q.poll();
				for (int i = 0; i < 4; i++) { // 4방탐색
					int nx = val[0]+dx[i];
					int ny = val[1]+dy[i];
					// board를 벗어나지 않으면서 상어가 움직일 수 있는 칸이라면
					if(0<=nx && nx <N && 0<= ny && ny <N && ! v[nx][ny] && shark.size>= board[nx][ny]) {
						int[] temp = {nx,ny};
						q.add(temp);
						v[nx][ny] = true;
						if(board[nx][ny] !=0 && shark.size>board[nx][ny]) { //해당 칸에 물고기가 있고 먹을 수 있으면
							int[] eatable = {nx,ny};
							eat_lst.add(eatable); // 거리가 같은 먹이 후보들
						}
					}
				}
			}
			
			// 먹이후보가 없다면 계속 먹이를 찾아나서야 함
			if(eat_lst.isEmpty())continue;

			// 먹이후보가 있다면 조건에 따라 정렬
			Collections.sort(eat_lst,new Comparator<int[]>(){
				@Override
				public int compare(int[] o1, int[] o2) {
					return (o1[0]==o2[0])?o1[1]-o2[1]:o1[0]-o2[0];
				}
			});
			
			// 우선순위가 가장 높은 먹이를 채택한다(selected fish)
			int[] s_fish = eat_lst.get(0);
			
			// 선택한 물고기를 상어가 먹는다.
			eat(shark,s_fish[0],s_fish[1]);
			
			// 먹기 위해 움직인 횟수
			// move_cnt += Math.abs(x-s_fish[0]) + Math.abs(y-s_fish[1]); // 못지나가는 칸이 있기 때문에 좌표로 계산하면 안되고 depth로 계산해야 함
			move_cnt += cnt; // cnt는 BFS의 depth
			return true; // 가장 거리가 짧은 먹이를 찾았기 때문에 더이상 BFS를 실행하지 않음(return), 먹이가 존재하기 때문에 true를 반환
		}
		return false; // BFS로 모든 board를 다 탐색했는데도 먹이가 없음
	}
	
	public static void eat(Baby shark,int x, int y) {
		++shark.eat_count; // 먹은 개수
		
		if(shark.eat_count == shark.size) { // 레벨업
			++shark.size;
			shark.eat_count = 0; // 먹은 개수 초기화
		}
		board[x][y] = 0; // 해당 물고기를 먹었다고 표시해 줌

		// 상어 위치 이동(여기서부터 다시 BFS시작)
		shark.x = x;
		shark.y = y;

		
	}
	
	static class Baby{
		int x;
		int y;
		int size;
		int eat_count;
		
		public Baby(int x, int y, int size, int eat_count) {
			super();
			this.x = x;
			this.y = y;
			this.size = size;
			this.eat_count = eat_count;
		}
		@Override
		public String toString() {
			return "baby [x=" + x + ", y=" + y + ", size=" + size + ", eat_count=" + eat_count + "]";
		}
		
	}
}

기타

• Comparator구현이 아직 미숙합니다. -> 복습하기