아기 상어

가장 중요한 핵심 - 완전탐색 반복⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️⭐️

1. 완전탐색을 반복해야한다!!!(인구이동과 똑같은 포인트에서 틀림⭐️) 인구이동 문제와 마찬가지로 완전탐색을 한번만 하는 게 아니라 문제에서 주어진 조건대로 계속해서 완전탐색을 반복해야한다! 재귀함수면 재귀함수, 큐while문이면 큐while문 자체를 반복해야한다! 무한루프(while(true) 또는 do-while(flag))를 만들고, 그 안에서 완전탬색을 반복하고, 문제 조건에 따라 종료 조건 구현해서 무한루프 탈출하는 식으로 구현해야한다!!! - 인구 이동 : 완탐 계속할수록 map이 계속 변함. - 아기 상어 : 완탐 계속할수록 상어크기 계속 변함. => 계속해서 완탐 반복하되, 문제에서 주어지는 조건에 따라 전체 반복문(무한루프)종료해야함!

2. 2. 상어가 벌크업하면 새로 탐색해야한다. visited도 초기화해야한다.(생각함. 구현X) 아래 코드에서 while(!q.isEmpty() 내부에 앞쪽에 visited초기화 부분을 넣었는데 이렇게 해버리면 큐가 비지 않는 동안 상어가 이동할 때마다 방문 체크 정보가 초기화되서 결국 노드들을 재방문하여 무한루프에 빠지게 된다!!!!!!!!!!!!!!!!!! visited 초기화 부분을 whlie(!q.isEmpty()) 밖으로 빼내자!

3. 큐BFS를 반복하는 조건과 이유, visited 초기화 시기 완전탐색은 먹을 물고기가 없을 때까지 계속해서 반복해야한다! 먹을 물고기가 곧 완전탐색 종료 조건이기 때문에 먹을 물고기들 정보를 저장해야한다!!!

• 전체 반복문 while문 생성

• 전체 반복문 while문 안에 큐BFS while문 : 먹을 물고기를 찾는 용도의 완전 탐색!

전체 반복문 while{
    물고기 찾는 완전탐색 while {...}
    //물고기 완전탐색 결과에 따른 처리
    1. 먹을 물고기 없는 경우 : 현재까지 time리턴 후 전체 반복문 종료
    2. 먹을 물고기 없는 경우 : 물고기 먹는 처리,
                    그 물고기 위치가 상어 위치가 되고, 다시 전체 반복문 while 반!
}

1. 로직 구현>물고기를 먹으면 그 물고기의 거리값 만큼 더해준다. 현재 아래 코드에서는 모든 (nx,ny)에 대해 ans를 다 1씩 증가시켰다. 먹을 수 있는 물고기 위치 nx,ny에 대해서만 해줘야한다!!!!! 할꺼면 5번째 줄처럼 먹는 물고기의 dist값을 더해줘야한다!!

   //물고기 먹는 처리.
   				if(map[nx][ny]<size) {
   					map[nx][ny] = 0;
   					cnt++;
   					ans += cur.dist;
   				}
   				if(cnt==size) {
   					size++;
   					cnt=0;
   				}

2. 문제점 : 물고기를 찾는 탐색과 물고기를 먹는 처리를 함께 처리하고 있다. => 로직을 분리한다! 솔루션 : while(!q.isEmpty)문에서는 먹을 물고기들 찾는 용도로만 완전탐색 진행 물고기 완전탐색 끝나면 탐색 결과에 따라 물고기 없는 경우(지금까지의 time을 리턴), 물고기 있는 경우 나눠서 처리해준다!!

3. 물고기 완전탐색, 물고기 먹기 => 얼마나 계속 반복해야할까? 반복 기준은 뭘까? => 물고기를 먹으면 그걸로 끝나는 게 아니라 먹은 물고기 위치에서 탐색 다시 시작한다.

4. 방문체크 처리❌ : 다음 방문할 노드 nx,ny 중복방문체크 안해줌. 큐에 넣을 때도 visited를 true로 마킹 안함.

package ss;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class BabyShark {
	static int n,size,cnt,ans;//전체 크기 n, 상어크기, 상어가 먹은 물고기 갯수 
	static int[][] map;
	static boolean[][] visited;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static class Pnt{
		int x,y,dist;
		Pnt(int x,int y,int dist){
			this.x = x;
			this.y = y;
			this.dist = dist;
		}
	}
	static Pnt shark;
	static int bfs() {
		ans = 0;
		Queue<Pnt> q = new LinkedList<>();
		q.add(shark);
		while(!q.isEmpty()) {
			//방문 배열 초기화=>where to put?!
			visited = new boolean[n][n];
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					visited[i][j] = false;
				}
			}
			Pnt cur = q.remove();
			
			for(int d=0;d<4;d++) {
				int nx = cur.x+dx[d];
				int ny = cur.y+dy[d];
				if(range_check(nx,ny))continue;
				if(map[nx][ny]>size) continue;
				ans++;//(nx,ny)로 이동할 때 ans(걸린 시간)를 증가시킨다.
				q.add(new Pnt(nx,ny,cur.dist+1));
				//물고기 먹는 처리.
				if(map[nx][ny]<size) {
					map[nx][ny] = 0;
					cnt++;
				}
				if(cnt==size) {
					size++;
					cnt=0;
				}
			}
		}
		return ans;
	}
	static boolean range_check(int x,int y) {
		return x<0 || y<0 || x>=n || y>=n;
	}
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		visited = new boolean[n][n];
		//초기 상어 크기, 먹은 물고기 갯수 초기화.
		size = 2; cnt = 0;
		for(int i=0;i<n;i++) {
			String[] input = br.readLine().split(" ");
			for(int j=0;j<n;j++) {
				map[i][j] = Integer.parseInt(input[j]);
				if(map[i][j]==9) {
					shark = new Pnt(i,j,0);
					map[i][j] = 0;
					//visited[i][j] = true;//이게 여기 꼭 있어야하나?BFS에서 map값이 0인 것은 안가도록 처리해주면 된다.
				}
			}
		}
	}

}