백준( BOJ ) 16236번 아기 상어

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

16236번: 아기 상어

 

풀이 :

9의 위치에서 BFS를 통해 갈 수 있는 위치를 파악하고 v 배열에 담은 후에 v 배열은 d, y, x 순이므로

 

정렬 시 자동으로 가장 짧은 값 중 위에 값 중 왼쪽에 있는 것을 고르게 된다.

 

v에 후보들은 우선 주어진 fish에서 0는 물고기가 없는 곳이니 제외, 물고기의 크기가 같은 것은 babysize.first 미만으로

 

제외,  가장 짧은 값을 판단하기 위한 d[i][j] 값을 넣어주었다.

 

이제 v 가 하나라도 있다면 가장 짧은 경로이므로 이동하고 다시 BFS를 통해 파악한다. 반복

 

 

코드 ( C++ )

	#include <algorithm>
	#include <queue>
	#include <vector>
	#include <iostream>
	#include <cstring>
	#include <tuple>
	using namespace std;
	int n;
	int fish[20][20];
	pair<int, int> babysize = { 2,0 };
	const int dy[4] = { 1,-1,0,0 };
	const int dx[4] = { 0,0, 1,-1 };
	int d[20][20];
	tuple<int,int> bfs(int i, int j)
	{
	memset(d, -1, sizeof(d));
	queue<pair<int, int>> q;
	q.push({ i,j });
	d[i][j] = 0;
	while (!q.empty())
	{
	int y = q.front().first;
	int x = q.front().second;
	q.pop();
	for (int k = 0; k < 4; ++k) {
	int ny = y + dy[k];
	int nx = x + dx[k];
	if (!(0 <= ny && ny < n && 0 <= nx && nx < n)) continue;
	if (fish[ny][nx] > babysize.first) continue;
	if (d[ny][nx] != -1) continue;
	q.push({ ny,nx });
	d[ny][nx] = d[y][x] + 1;
	}
	}
	// d, y, x
	vector<tuple<int,int, int>> v;
	for(int i=0; i<n; ++i)
	for (int j = 0; j < n; ++j) {
	if (fish[i][j] > 0 && fish[i][j] < babysize.first && d[i][j]> 0) {
	v.push_back({d[i][j], i,j });
	}
	}
	// 정렬
	sort(v.begin(), v.end());
	if (v.size() > 0) {
	int d, y, x;
	tie(d, y,x) = v[0];
	return { y, x };
	}
	else
	return { -1,-1 };
	}
	int main()
	{
	cin >> n;
	int fy, fx;
	for(int i=0; i<n; ++i)
	for (int j = 0; j < n; ++j) {
	cin >> fish[i][j];
	if (fish[i][j] == 9) {
	fy = i;
	fx = j;
	}
	}
	int sum = 0;
	while (1)
	{
	int y, x;
	tie(y, x) = bfs(fy, fx);
	if (y == -1 && x == -1) {
	break;
	}
	else {
	sum += d[y][x];
	fish[fy][fx] = 0;
	fish[y][x] = 9;
	fy = y;
	fx = x;
	babysize.second += 1;
	if (babysize.second == babysize.first) {
	babysize.first += 1;
	babysize.second = 0;
	}
	}
	}
	cout << sum << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub