백준 16236 아기 상어

 

아기 상어가 물고기를 먹는 문제입니다. 단순 bfs 문제이긴 하지만 생각보다 이것저것 귀찮은 문제입니다.

 

먼저 상어는 자기보다 작은 물고기를 먹고 자신의 크기만큼 물고기를 먹으면 크기가 증가하므로 이를 저장하기 위해서 구조체를 하나 만들었습니다. 구조체에 상어의 좌표와 크기, 현재까지 먹은 물고기 수를 저장하고 bfs를 진행하여 돌리며 먹을 수 있는 가장 가까운 물고기를 찾습니다. 이때 먹을 수 있는 물고기가 여러마리라면 물고기의 좌표(x,y)가 작은 물고리를 먼저 먹어야 하므로 각 싸이클을 한번 모두돌면서 가장 좌표가 작은 물고기를 찾아서 먹어주면 되겠습니다.

 

이런 문제는 항상 꼼꼼하게 구현하는 것이 중요한 것 같습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct shark{
	int x,y;
	int size;
	int cur;
	
}shark;

int maze[21][21];
int N;
vector<pair<int, pair<int,int>> > fish;
pair<int,int> curfish;

int nextx[4] = {1,-1,0,0};
int nexty[4] = {0,0,1,-1};
int ans;


bool sol() {
		
	queue<pair<int, int> > q; // 좌표 
	q.push({shark.x, shark.y}); 
	curfish.first = 30;
	curfish.second = 30;		
	int visited[21][21] = {0, };
	visited[shark.x][shark.y] = 1;
	int cnt = 0;	
	int curcnt;
	bool flag = false;	
		
	while(!q.empty()) {	
		int len = q.size();		
		for(int i = 0; i < len; i++) {
			int x = q.front().first;
			int y = q.front().second;					
			q.pop();			
			for(int j = 0; j < 4; j++) {
				int xx = x + nextx[j];
				int yy = y + nexty[j];
				
				if(xx < 0 || xx > N-1 || yy < 0 || yy > N-1) continue;
				
				if(maze[xx][yy] > shark.size || visited[xx][yy]) continue;
				
				if(maze[xx][yy] != 0 && maze[xx][yy] < shark.size) {				
					flag = true;		
					
					if(curfish.first == 30) {																				
						curfish.first = xx;
						curfish.second = yy;	
						curcnt = cnt+1;									
					}				
					else if(curfish.first > xx) {
						curfish.first= xx;
						curfish.second = yy;																
					}
					else if(curfish.first == xx && curfish.second > yy) {
						curfish.first= xx;
						curfish.second = yy;																
					}
						
				}
			
				visited[xx][yy] = 1;					
				q.push({xx,yy});				
			}
								
		}		
		cnt++;	
		if(flag) break;		
	}
	
	if(curfish.first == 30) { //물고기 못먹은경우 
		return false;
	}
	else {
		maze[curfish.first][curfish.second] = 0;
		shark.x = curfish.first;
		shark.y = curfish.second;
		shark.cur++;
		if(shark.cur == shark.size) {
			shark.size++;
			shark.cur = 0;
		}				
		ans += curcnt;	
		return true;
	}
	
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	
	cin >> N;
	
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < N; j++) {	
			cin >> maze[i][j];
			if(maze[i][j] == 9) {
				maze[i][j] = 0;				
				shark.x = i;
				shark.y = j;
				shark.size = 2;
				shark.cur = 0;
			}							
		}
	}
	
	while(1) {				
		if(!sol()) break;
	}
	cout<<ans;
	return 0;
}