백준 16236 [아기 상어] - JAVA

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

16236번: 아기 상어

풀이

1. 상어의 위치부터 시작한다.

2. 상어를 기준으로 Queue에 이동가능한 좌표를 +1씩 하면서 add한다.

3. 모든 맵을 순회하면서(BFS) 먹을 수 있는 물고기의 좌표는 따로 리스트에 담는다.

   이중 가장 가까운 물고기를 사냥한다.

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {

	static int N;
	static int[][] arrMap;
	static Node shark;
	static List<Node> eatingFishList = new ArrayList<Node>(); //사냥리스트
	static Queue<Node> q;
	static boolean[][] arrVisit;	//방문유무
	static int row[] = {0, 0, -1, 1};
	static int col[] = {-1, 1, 0, 0};
	static int nSize = 2;
	static int nEatCnt = 0;
	static int nTime = 0;
	
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] input = br.readLine().split(" ");
		N = Integer.parseInt(input[0]);
		arrMap = new int[N][N];
		arrVisit = new boolean[N][N];
		
		for(int nRow = 0 ; nRow < N ; nRow++) {
			input = br.readLine().split(" ");
			for(int nCol = 0 ; nCol < N ; nCol++) {
				arrMap[nRow][nCol] = Integer.parseInt(input[nCol]);
				
				if(arrMap[nRow][nCol] == 9) {
					shark = new Node(nRow, nCol, 0);
					arrMap[nRow][nCol] = 0;
				}
			}
		}
		
		doHunting();
		
		System.out.println(nTime);
	}
	
	private static void doHunting() {
    	//상어위치부터 BFS시작
		q = new LinkedList<Node>();
		q.add(shark);
		arrVisit[shark.row][shark.col] = true;
		
		while(true) {
			while(!q.isEmpty()) {
				Node cur = q.poll();
				for(int nIdx = 0 ; nIdx < 4 ; nIdx++) {
					int nMapRow = cur.row + row[nIdx];
					int nMapCol = cur.col + col[nIdx];
					
					//map범위밖
					if((nMapRow < 0 || nMapCol < 0 || nMapRow >= N || nMapCol >= N) ) {
						continue;
					}
					//이미방문한 곳
					if(arrVisit[nMapRow][nMapCol] == true) {
						continue;
					}
					
					//식사가능
					if(arrMap[nMapRow][nMapCol] < nSize && arrMap[nMapRow][nMapCol] != 0) {
						eatingFishList.add(new Node(nMapRow, nMapCol, cur.dist + 1));
						q.add(new Node(nMapRow, nMapCol, cur.dist + 1));
						arrVisit[nMapRow][nMapCol] = true;
					}
					//식사불가능, 이동가능
					if(arrMap[nMapRow][nMapCol] == nSize || arrMap[nMapRow][nMapCol] == 0) {
						q.add(new Node(nMapRow, nMapCol, cur.dist + 1));
						arrVisit[nMapRow][nMapCol] = true;
					}
				}
			}
			
			//먹을 물고기가 없다면
			if(eatingFishList.size() == 0) {
				return;
			}
			
            //사냥
			eating();
			
		}
	}

	private static void eating() {
    	//사냥할 물고기 선택
		Node eatingFish = eatingFishList.get(0);
		for(int nIdx = 1 ; nIdx < eatingFishList.size() ; nIdx++) {
			if(eatingFish.dist > eatingFishList.get(nIdx).dist) {
				eatingFish = eatingFishList.get(nIdx);
			}
			else if(eatingFish.dist == eatingFishList.get(nIdx).dist) {
				//가장위에있는 물고기
				if(eatingFish.row > eatingFishList.get(nIdx).row) {
					eatingFish = eatingFishList.get(nIdx);
				}
				else if(eatingFish.row == eatingFishList.get(nIdx).row) {
					//가장왼쪽에있는 물고기
					if(eatingFish.col > eatingFishList.get(nIdx).col) {
						eatingFish = eatingFishList.get(nIdx);
					}
				}
			}
		}
		
		nTime += eatingFish.dist;
		nEatCnt++;
		arrMap[eatingFish.row][eatingFish.col] = 0;	//사냥했기에 0으로 초기화
		eatingFishList.clear();	//먹이리스트 초기화
		
		if(nEatCnt == nSize) {
			nSize++;
			nEatCnt = 0;
		}
		
		//상어위치 초기화
		q.clear();
		arrVisit = new boolean[N][N];
		q.add(new Node(eatingFish.row, eatingFish.col, 0));
		
	}

	private static class Node{
		int row;
		int col;
		int dist;
		
		public Node (int row,int col,int dist) {
			this.row = row;
			this.col = col;
			this.dist = dist;
		}
	}
}