BOJ16236 아기상어

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

 

 

BFS를 사용하고 정렬과 구현이 필요한 문제다.

 

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

public class Main {
	
	static int n;
	static int[][] map;
	static Node shark;
	
	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];
		for(int i=0; i<n;i++) {
			String[] temp = br.readLine().split(" "); 
			for(int j=0; j<n; j++) {
				map[i][j] = Integer.parseInt(temp[j]);
				if(map[i][j] == 9) {
					shark = new Node(i,j,2,0);
					map[i][j]=0;
				}
			}
		}
		
		
		int ans = 0;
		int eat_count=0;
		while(true){
			// 그중 제일가까운 물고기 선택 
			Node found_fish = find_fish(shark);

			//먹을 수 없다면 break;
			if( found_fish == null) {
				break;
			}
			// 물고기 섭취수 증가  
			eat_count++;
			
			
			// 사이즈만큼의 물고기를 먹으면 사이즈 1 증가, 섭취수0으로 초기화 
			if(eat_count==shark.size) {
				eat_count=0;
				shark.size++;
			}
			
			//물고기 빈칸으로 만들기 
			map[found_fish.r][found_fish.c]=0;
			
			//상어 위치 이동 
			shark.r = found_fish.r;
			shark.c = found_fish.c;
			
			ans+=found_fish.step;
		}
		
		System.out.println(ans);

			
	}
	
	


	public static Node find_fish(Node start){
		List<Node> arr= new ArrayList<>();
		int result_step=500;
		boolean[][] visited = new boolean[n][n];
		int[] move_r = {1,-1,0,0};
		int[] move_c = {0,0,1,-1};
		Queue<Node> q = new LinkedList();
		q.offer(start);
		visited[start.r][start.c]=true;
		while(!q.isEmpty()) {

			Node now = q.poll();
			if(result_step< now.step) {
				Collections.sort(arr,(n1, n2) -> {
					if(n1.r==n2.r) {
						return n1.c-n2.c;
					}
					return n1.r-n2.r;
				});
				return arr.get(0);
			}
			
			if(map[now.r][now.c]!=0 && map[now.r][now.c]<shark.size) {
				arr.add(now);
				result_step = now.step;
				
			}
			
			for(int i=0;i<4;i++) {
				Node next= new Node(now.r+move_r[i], now.c+move_c[i],0,now.step+1);
				
				if( next.r<0 || next.r>=n || next.c<0 || next.c>=n || visited[next.r][next.c] || map[next.r][next.c]>shark.size) {
					continue;
				}
				
				visited[next.r][next.c]=true;
				q.offer(next);
				
			}
		}

		
		
		if(arr.isEmpty()) {
			return null;
		}else {
			Collections.sort(arr,(n1, n2) -> {
				if(n1.r==n2.r) {
					return n1.c-n2.c;
				}
				return n1.r-n2.r;
				
			});
			return arr.get(0);
		}
	}
	
	
	public static class Node{
		int r;
		int c;
		int size;
		int step;
		
		public Node(int r, int c, int size, int step) {
			this.r = r;
			this.c = c;
			this.size=size;
			this.step=step;
		}
		
		public String toString() {
			return "["+r+", "+c+", "+step+"]";
		}
	}

}