BOJ 16236 - 아기 상어

문제 링크(Link)

---

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

문제 해결(Solution)

---

 반복적인 BFS와 Sort를 이용해서 문제를 해결한다. 단, 구현이 까다롭다.

주의할 점 || 생각해볼 점(Caution || Consideration)

---

 1. 생각해야하는 조건

  : 이 문제는 생각해야하는 조건들이 많다. 그 중 가장 까다로운 것이 '어떤 물고기를 먹을 것인가?' 다. 이는 vector를 이용해서 쉽게 해결할 수 있다. vector<pair<int, pair<int, int> > >를 해서 거리, row, col 순으로 저장하면 단순한 sort함수를 통해서 다음에 먹을 물고기를 쉽게 찾을 수 있다.

 2. 시간 복잡도는? 

  :  인접행렬로 구현했기 때문에 BFS는 N^2, sort() 함수를 사용했기 때문에 정렬은 NlgN. 그러므로 시간복잡도는 O(N^3*lgN) 

참고(Reference)

---

 - 

	#include<cstdio>
	#include<iostream>
	#include<map>
	#include<algorithm>
	#include<vector>
	#include<cstring>
	#include<string>
	#include<queue>
	using namespace std;
	typedef struct{
	int _size;
	int pos_x;
	int pox_y;
	int eat;
	}FISH;
	FISH baby;
	int N;
	int a[25][25];
	int row_move[]={-1,1,0,0};
	int col_move[]={0,0,-1,1};
	int ans;
	bool visit[25][25];
	bool findFish(){
	memset(visit,false,sizeof(visit));
	vector<pair<int,pair<int,int> > > vt;
	queue<pair<int,pair<int,int> > > q;
	visit[baby.pos_x][baby.pox_y]=true;
	q.push({0,{baby.pos_x,baby.pox_y}});
	while(!q.empty()){
	int row = q.front().second.first;
	int col = q.front().second.second;
	int dist = q.front().first;
	q.pop();
	if(a[row][col]!=9 && a[row][col]!=0 && a[row][col]<baby._size){
	vt.push_back({dist,{row,col}});
	}
	for(int i=0;i<4;i++){
	int nrow = row + row_move[i];
	int ncol = col + col_move[i];
	int ndist = dist+1;
	if(nrow<0||nrow>=N||ncol<0||ncol>=N) continue;
	if(visit[nrow][ncol]) continue;
	if(a[nrow][ncol]>baby._size) continue;
	visit[nrow][ncol]=true;
	q.push({ndist,{nrow,ncol}});
	}
	}
	if(!vt.size())
	return false;
	// caution 1
	sort(vt.begin(),vt.end());
	baby.eat++;
	if(baby.eat==baby._size){
	baby.eat=0;
	baby._size++;
	}
	a[baby.pos_x][baby.pox_y]=0;
	baby.pos_x=vt[0].second.first;
	baby.pox_y=vt[0].second.second;
	ans+=vt[0].first;
	a[baby.pos_x][baby.pox_y]=9;
	return true;
	}
	int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;
	baby._size=2;
	baby.eat=0;
	for(int i=0;i<N;i++){
	for(int j=0;j<N;j++){
	cin >> a[i][j];
	if(a[i][j] == 9){
	baby.pos_x=i;
	baby.pox_y=j;
	}
	}
	}
	while(findFish());
	cout << ans;
	return 0;
	}

view raw BOJ 16235.cpp hosted with ❤ by GitHub

※ 정확하고 부드러운 태클은 언제나 환영입니다.