백준 16236번 아기상어

www.acmicpc.net/problem/16236

16236번: 아기 상어

오늘 풀어본 문제는 백준의 16236번 아기상어입니다.

알고리즘 분류는 아래와 같습니다.

• 구현
• 그래프 이론
• 그래프 탐색
• 시뮬레이션
• 너비 우선 탐색

답으로 상어가 먹을 수 있는 먹이가 다 떨어지는 시점을 제출해야합니다.

제가 구현한 부분은 다음과 같습니다.

• 상어에게서 가장 가까운 다음 물고기 찾기(물고기 먹을 때마다 BFS를 통해 거리 계산)
• BFS를 하는 동안 이동하는 칸이라면 이동 경로 큐에 물고기라면 물고기 어레이리스트에 넣음
• 먹을 수있는 가장 가까운 물고기가 여러 개일 경우 우선 순위 계산(Comparable로 해결)후 정렬
• 우선 순위가 가장 높은 물고기 먹기(상어 이동, 칸 비우기, 방문 확인 배열 초기화) 
• 물고기를 먹은 갯수가 자신의 크기와 같은 수가 될때 마다 물고기의 크기 키우기

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

import javax.print.attribute.standard.Finishings;

//백준 아기상어 16236
public class BabyShark16236 {
	int n , time = 0, fishNum = 0, eatCount = 0 ,sharkVal = 2;
	int[][] map;
	boolean[][] visited;
	boolean canEat = true;
	Points sharkPoint;
	ArrayList<Points> fishs = new ArrayList<>();
	Queue<Points> loadQueue = new LinkedList<>();
	
	//숫자 입력
	public void setNum() {
		int i, j;
		try {
			BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer st = new StringTokenizer(bf.readLine());
			
			n = Integer.parseInt(st.nextToken());
			
			map = new int[n][n];
			visited = new boolean[n][n];
			
			for(i = 0; i<n; i++) {
				st = new StringTokenizer(bf.readLine());
				
				for(j=0; j<n; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					
					if(map[i][j] == 9) {
						sharkPoint = new Points(i, j);
						map[i][j] = 0;
					}else if(map[i][j] != 0) {
						fishNum++;
					}	
				}
			}
		}catch (Exception e) {
			// TODO: handle exception
		}
	}
	
	//다음 물고기 찾기
	public void searchFish() {
		int i,j, queueSize, x, y;
		Points nowPoint;
		loadQueue.add(sharkPoint);
		visited[sharkPoint.y][sharkPoint.x] = true;
		int distance = 0;
		

		while(!loadQueue.isEmpty()) {
			distance++;
			queueSize = loadQueue.size();
			
			for(i=0; i<queueSize; i++) {
				nowPoint = loadQueue.remove();
				
				x = nowPoint.x;
				y = nowPoint.y;
				
				if(y+1 < n && !visited[y+1][x] && map[y+1][x] <= sharkVal) {
					checkFish(y+1, x);
				}if(y -1 >= 0 && !visited[y-1][x] && map[y-1][x] <= sharkVal) {
					checkFish(y-1, x);
				}if(x + 1 < n &&!visited[y][x+1] && map[y][x+1] <= sharkVal) {
					checkFish(y, x+1);
				}if(x-1 >= 0 && !visited[y][x-1] && map[y][x-1] <= sharkVal) {
					checkFish(y, x-1);
				}
			}
			if(!fishs.isEmpty()) {
				break;
			}
		}
		loadQueue.clear();
		if(!fishs.isEmpty()) {
			time += distance;
		}else {
			canEat = false;
		}
		
	}
	
	public void eatFish() {
		int i, j;
		fishs.sort(Comparator.naturalOrder());
		Points eatFishPoint = fishs.get(0);
		
		sharkPoint = eatFishPoint;
		map[sharkPoint.y][sharkPoint.x] = 0;
		
		eatCount++;
		fishNum--;
		if(eatCount%sharkVal == 0) {
			eatCount = 0;
			sharkVal++;
		}
		
		fishs.clear();
		for(i=0; i<n; i++)
			Arrays.fill(visited[i], false);
	}
	
	public void checkFish(int y, int x) {
		visited[y][x] = true;
		if(sharkVal > map[y][x] && map[y][x] != 0) {
			fishs.add(new Points(y, x));
		}else {
			loadQueue.add(new Points(y, x));
		}
	}
	
	public class Points implements Comparable<Points>{
		int x,y, distance;
		public Points(int y, int x) {
			this.x = x;
			this.y = y;
		}
		
		@Override
		public int compareTo(Points o) {
			// TODO Auto-generated method stub
			
	
		if(this.y > o.y) {
			return 1;
		}else if(this.y < o.y) {
			return -1;
		}else if(this.y == o.y) {
			if(this.x > o.x) {
				return 1;
			}else{
				return -1;
			}
		}
		
		return 0;
		}		
	}
	
	
	
	public static void main(String args[]) {
		BabyShark16236 main = new BabyShark16236();
		main.setNum();
		boolean canEat;
		//System.out.println(main.fishNum);
		while(main.fishNum != 0) {
			main.searchFish();
			
			if(!main.canEat)
				break;
			else {
				main.eatFish();
			}
		}
		System.out.println(main.time);
	
	}
}

반성할 점

• 변수가 너무 많아져 나도 헷갈린다.
• 노트에 적으면서 정리하면서 코드 짜기
• 시간 복잡도 공간 복잡도 계산하면서 하기