백준 16236. 아기상어 (Gold3, SW)

정답코드

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

//아기상어 객체를 만들어서 i,j 값을 저장한다. pair 쓰기싫어,,,
public class BabyShark {
	static class fish{
		int i;
		int j;
		
		public fish(int i,int j) {
			this.i = i;
			this.j = j;
		}
	}
	
	static int [][] ocean;
	static int N;
	static int SharkSize = 2;
	static int time = 0;
	
	static ArrayList<fish>compute = new ArrayList<>();
	static int s_i,s_j;  //상어의 좌표 
	static int distance[][];
	static int di; 

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		ocean = new int[N][N];
		fish shark = null;
		
		for(int  i = 0; i < N; i++) {
			String [] input = br.readLine().split(" ");
			for(int  j = 0; j < N; j++) {
				fish f = new fish(i,j);
				int now_fish = Integer.parseInt(input[j]);
				ocean[i][j] = now_fish;
					//숫자가 9이면 상어 좌표를 저장
			    if (now_fish == 9) {
					s_i = i;
					s_j = j;
				}
			}
		}
		
		
		shark = new fish(s_i,s_j);
		int eat_count = 0;
		
	  //먹을 수 있는 물고기가 없을 때 까지 먹는다 
		while(true) {
			compute(shark);
			//check에서 자기보다 크기가 작은 물고기가 있는지 체크 
			if(check()==0)break;
			eatFish();
			
			//물고기 크기는 6이하 so 7이상에선 굳이 더 무게를 키울 필요는 없다
			if(SharkSize <= 7)eat_count++;
			time+=di;
			
			//자기 몸무게 만큼 먹으면 상어사이즈를 ++ 해준다
			if(eat_count == SharkSize) {
				eat_count = 0;
				SharkSize++;
			}
			shark = new fish(s_i,s_j);
		}
		System.out.println(time);
		
	}
	
	//BFS로 문제 접근하기 배열의 모든 곳에 대해서 도달거리 구하기 
	public static void compute(fish shark) {
		
		int dx[] = {-1,1,0,0};
		int dy[] = {0,0,-1,1};
		
		
		Deque<fish>dq = new ArrayDeque<>();
		dq.add(shark);
		
		distance = new int [N][N];
		boolean visited[][] = new boolean[N][N];
		visited[s_i][s_j] = true;
		
		while(!dq.isEmpty()) {
			
			fish now = dq.removeFirst();
			int x = now.i;
			int y = now.j;
			
			for(int i = 0; i < 4; i++) {
				int nx = x+dx[i];
				int ny = y+dy[i];
				
				//범위를 벗어나면 넘어간다 
				if(nx >= N || nx < 0 || ny >= N|| ny < 0)continue;
				//if 방문한 곳이면 넘어간다 
				if(visited[nx][ny] == true)continue;
				//if 지나갈 수 없는 길이라면 넘어간다 
				if(ocean[nx][ny] > SharkSize)continue; 
				
				visited[nx][ny] = true;
				
				//다음에 지나갈 idx = 지금 idx + 1
				distance[nx][ny] = distance[x][y]+1;
				fish f = new fish(nx,ny);
				dq.add(f);
			}	
		}
	}
	
	//가장 가까운 거리에 있는 먹을 수 있는 물고기를 먹는다 
	static public void eatFish() {
		
		int eat_x = 0, eat_y = 0;
		di = Integer.MAX_VALUE; 
		
		//거리가 같으면 윗쪽에 있는 (i값이 작은) 같다면 왼쪽에 있는(j값이 작은) 물고기를 먹는다 
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				//distance =0 이거나, 물고기가 없는 지역이거나 자기 크기보다 크면  continue
				if(distance[i][j]==0 || ocean[i][j]==0 ||ocean[i][j]>=SharkSize )continue;
				
				//이전에 측정된 최솟값 보다 작을 때 더 작은 거리에 있는 물고기를 먹는다 
				if(distance[i][j]<di) {
					eat_x = i;
					eat_y = j;
					di = distance[i][j];
				}
				
				//distance가 같을 때는 조건을 만들 필요가 없다 왜냐면 for문 자체가 열을 늘리고 행을 늘리면서 보기 때문에 조건과 동일 
				
			}
		}		
		
		if(di == Integer.MIN_VALUE)return;
		
		//물고기를 먹고나서 원래 상어자리를 0 움직인 상어 자리를 9로 바꿔준다 
		ocean[s_i][s_j] = 0;
		ocean[eat_x][eat_y] = 9;
		s_i = eat_x;
		s_j = eat_y;
	}
	
	//자기보다 작은 물고기가 있는지 & 도달가능한지 체크 
	static public int check() {
		int cnt = 0;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(ocean[i][j] < SharkSize && ocean[i][j] != 0 && distance[i][j]!=0) {
					cnt++;
				}
			}		
		}
		
		return cnt;
	}
	
}

전략

• 처음에는 물고기 크기별로 리스트에 저장해두고 상어보다 크기가 작은 물고기들에 대해서 계산을 하면 더 빠를 거 같아서 하다가 결국 시간이 더 걸릴 거 같아서 엎음

  • BruteForce 기본으로 돌아가자

• 최단거리 문제가 나오면 항상 BFS! BFS로 상어가 갈 수 있는 거리에 대해서 최단 거리를 각각 구한다 → 여기서 세부조건들을 하나하나 따져서 구현하는게 조금 시간이 걸림

• 항상 물고기를 먹고난 다음에 먹을 수 있는 물고기가 있는지 백트래킹을 해야지 시간초과가 나지 않는다