[백준] 16236번 아기상어

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int [] dy = {0,0,1,-1};
	static int [] dx = {1,-1,0,0};
	static Shark bfs(int [][]a,int sy,int sx,int size) {
		int n = a.length;
		ArrayList<Shark> arr = new ArrayList<>();
		int [][] d = new int [n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				d[i][j] = -1;
			}
		}
		Queue<Integer> q = new LinkedList<>();
		q.add(sy);q.add(sx);
		d[sy][sx] = 0;
		while(!q.isEmpty()) {
			int y = q.remove();
			int x = q.remove();
			for (int i = 0; i < 4; i++) {
				int ny = y+dy[i];
				int nx = x+dx[i];
				// 아직 아무것도 접근하지 않았던 상태일 때,
				if(0<=ny && ny<n && 0<=nx && nx<n && d[ny][nx]==-1) {
					boolean ok = false;
					boolean eat = false;
					if(a[ny][nx]==0) {
						ok= true;
					}else if(a[ny][nx] == size) {
						ok = true;
					}else if(a[ny][nx]<size) {
						ok= true;
						eat=true;
					}
					if(ok) {
						q.add(ny);q.add(nx);
						d[ny][nx] = d[y][x] +1;
						if(eat) {
							arr.add(new Shark(d[ny][nx],ny,nx));
						}
					}
				}
			}
		}
		if(arr.isEmpty()) {
			return null;
		}
		Shark best = arr.get(0);
		for(Shark s : arr) {
			if(best.dist>s.dist) {
				best = s;
			}else if(best.dist == s.dist && best.y > s.y) {
				best = s;
			}else if(best.dist == s.dist && best.y == s.y && best.x>s.x) {
				best = s;
			}
		}
		return best;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int [][] a = new int [n][n];
		int y = 0,x = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				a[i][j] = sc.nextInt();
				if(a[i][j]==9) {
					y=i;x=j;
					// 상어는 자리에서 뺴준다.. 물고기들만 남았다..!
					a[i][j] = 0;
				}
			}
		}
		int ans = 0;
		int size = 2;
		int exp = 0;
		while(true) {
			// 목표에 맞는 물고기 포착했따.
			Shark s = bfs(a,y,x,size);
			if(s == null) {
				break; // 없다면 빠져나가기
			}
			a[s.y][s.x]= 0; // 먹잇감 0 으로 만들어주기.
			ans += s.dist;
			exp+=1;
			if(size==exp) {
				exp=0;
				size++;
			}
			y = s.y;
			x = s.x;
		}
		System.out.println(ans);
	}
	static class Shark{
		int dist,y,x;

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

포인트 : bfs 사용하기

bfs 해서 가져온 가장 최적의 물고기값을 먹을 때, 상어가 변하는 과정을 무한루프 돌린다.
다 먹거나 먹을 수 없는 물고기만 남았을 경우, 해당 거리까지를 더해준 것을 출력한다.

 

c++ 코드로 작성한 아기상어.

#include<iostream>
#include<algorithm>
#include<tuple>
#include<vector>
#include<queue>

using namespace std;
int row[] = { 0,0,-1,1 };
int col[] = { -1,1,0,0 };
tuple<int, int, int>bfs(vector<vector<int>>a, int y, int x, int size) {
	int n = a.size();
	vector<vector<int>> d(n, vector<int>(n, -1));
	vector<tuple<int, int, int>> ans;
	queue<pair<int, int>>q;
	q.push(make_pair(y, x));
	d[y][x] = 0;
	while (!q.empty()) {
		tie(y, x) = q.front();
		q.pop();
		for (int i = 0; i < 4; i++){
			int ny = y + row[i];
			int nx = x + col[i];
			if (0 <= ny && ny < n && 0 <= nx && nx < n && d[ny][nx] == -1) {
				bool ok = false;
				bool eat = false;
				if (a[ny][nx] == size) {
					ok = true;
				}
				else if (a[ny][nx] == 0) {
					ok = true;
				}
				else if (a[ny][nx] < size) {
					ok = eat = true;
				}
				if (ok) {
					q.push(make_pair(ny, nx));
					d[ny][nx] = d[y][x] + 1;
					if (eat) {
						ans.push_back(make_tuple(d[ny][nx],ny,nx));
					}
				}
			}
		}
	}
	if (ans.empty()) {
		return make_tuple(-1, -1, -1);
	}
	else {
		sort(ans.begin(), ans.end());
		return ans[0];
	}
}
int main() {
	int n;
	cin >> n;
	vector<vector<int>> a(n, vector<int>(n, 0));
	int x, y;
	int size = 2;
	int exp = 0;
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
			if (a[i][j] == 9) {
				a[i][j] = 0;
				tie(y, x) = make_pair(i, j);
			}
		}
	}

	while (true) {
		int ny, nx, dist;
		tie(dist, ny, nx) = bfs(a, y, x, size);
		if (dist == -1)break;
		ans += dist;
		a[ny][nx] = 0;
		exp++;
		if (size == exp) {
			size++;
			exp = 0;
		}
		tie(y, x) = make_pair(ny, nx);
	}
	cout << ans << endl;
	return 0;
}