[삼성SW테스트] 백준 16236 아기상어(BFS)

백준 BFS 문제

#16236- 아기상어

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

사용한 개념

BFS개념을 사용했고, 문제 안에 있는 단계적인 스텝은 시뮬레이션으로 구현했습니다. 시뮬레이션이라고 하면, for문 if문 등 조건/반복문을 열심히...코딩해서 구현하는 것을 뜻합니다 ㅎㅎ...

음..해당 문제에서 주어지는 요구사항을 저는 아래의 메커니즘으로 구현했습니다.

1. 먹을 수 있는 물고기를 전부 일괄 저장해논다!

2. 먹을 수 있는 물고기들끼리 가장 먼저 우선해서 먹어야할 하나의 물고기만 선별! 

(선별조건은 문제에 있습니다.)

3. 물고기 먹은 횟수 증가 및 나이를 증가해야하는지 여부 체크!

4. 먹을 물고기 위치에서 다시 상어를 위치시키고, 1번 스텝 반복!

여기서 이동할 때 포인트는 자기자신보다 같거나 빈공간이면 이동이 가능하단 점!! 잊지마세요.

더 필요한 개념은 없습니다. 다만, BFS탐색할때 탐색조건을 장황하게 설명해놓은 것일 뿐이죠...

그래서 생각보다 머리가 아팠던 문제였네요.....

아래는 전체소스입니다. 궁굼하신 점은 댓글 남겨주세요~

전체소스

import java.util.LinkedList;
import java.util.Scanner;
public class BackJoon_16236 {

	static int sea[][];
	static int n = 0;
	static int dX[] = {-1,0,1,0};
	static int dY[] = {0,1,0,-1};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		
		sea = new int[n][n];

		//1. 먹을 물고기 있는지 탐색
		//1-1. 제일 가까운 물고기 탐색은 자연스럽게 BFS로 해결, 만약 먹을 물고리 동률-> 가장위 -> 가장 왼쪽
		//2. 먹을 물고기 찾으면,먹고 나이증가 체크
		//3. 큐에 있는 모든 포인트 날리고 현재 찾은 포인트만 add
		LinkedList<Shark> q = new LinkedList<>();
		int age = 2;
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				sea[i][j] = sc.nextInt();
				if(sea[i][j] == 9){
					q.add(new Shark(i, j, age));
					sea[i][j] = 0;
				}
			}
		}
		int eat = 0;
		int time = 0;	
		while(true){
			Shark sShk = q.peek();
			LinkedList<Shark> fish = new LinkedList<>();
			int [][] dist = new int[n][n];// 거리

			while (!q.isEmpty()) {
				Shark s = q.poll();
				for(int i=0; i<4; i++){
					int nX = s.x + dX[i];
					int nY = s.y + dY[i];
				
					if(-1<nX && nX<n && -1<nY && nY<n && dist[nX][nY]==0 && sea[nX][nY] <= age){
						dist[nX][nY] = dist[s.x][s.y] + 1;
						//먹잇감 포착
						if(1<=sea[nX][nY] && sea[nX][nY]<=6 && sea[nX][nY] < age){
							fish.add(new Shark(nX, nY, dist[nX][nY]));
							q.add(new Shark(nX, nY, dist[nX][nY]));
							continue;
						} 
						//먹잇감 없음(지나가긴함)
						q.add(new Shark(nX, nY, dist[nX][nY]));
					}
				}
			}

			//제일 가까운..
			if(fish.size() == 0){
				System.out.println(time);
				return;
			}
			int d = 5000;
			Shark eatingFish = fish.get(0);
			for(int i=1; i<fish.size(); i++){
				if(eatingFish.dist > fish.get(i).dist) {
					eatingFish = fish.get(i);
				}
				
				if(eatingFish.dist == fish.get(i).dist) {
					if(eatingFish.x > fish.get(i).x){
						eatingFish = fish.get(i);
						continue;
					}else if(eatingFish.x == fish.get(i).x){
						if(eatingFish.y > fish.get(i).y);
						eatingFish = fish.get(i);	
					}
				}	
			}
			
			time += eatingFish.dist;
			eat++;
			sea[eatingFish.x][eatingFish.y] = 0;
			if(eat == age) {
				age++;
				eat = 0;
			}
			q.add(new Shark(eatingFish.x, eatingFish.y, age));

		}
	
			
	}
}
	


	class Shark{
		int x;
		int y;
		int dist;
		public Shark(int x, int y, int dist) {
			super();
			this.x = x;
			this.y = y;
			this.dist = dist;
	}
}