[ Baekjoon ] 16236. 아기 상어

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

16236번: 아기 상어

풀이 방법

물고기를 먹으려할 때마다 BFS를 이용해서 어떤 물고기를 먹을지 결정한다. 더 이상 먹을 수 있는 물고기가 없으면 종료한다.

 

BFS를 사용하여 탐색할 때 큐에 행, 열, 아기 상어로부터의 거리를 추가한다.

queue< tuple<int, int, int> > q;

 

아기 상어로부터 거리가 동일한 물고기가 여러 개 존재하면 더 작은 행에 위치하고, 동일한 행에 존재하면 더 작은 열에 존재하는 물고기를 선택해야 한다. 따라서 탐색을 하다가 물고기를 발견하면 다음과 같이 물고기 정보를 임시 저장한다.

// update fish to eat
if(sea[row][col] > 0 && sea[row][col] < size){
	if(fish_r > row || (fish_r == row && fish_c > col)){
		min_dist = dist;
		fish_r = row;
		fish_c = col;
	}
}

 

탐색하는 칸까지의 거리가 min_dist보다 커지면 BFS를 종료한다.

if(dist > min_dist) break;

---

BFS를 종료한 후, 선택한 물고기로 현재 아기 상어의 위치를 옮기고 시간과 아기 상어의 크기를 업데이트한다.

// move to the fish and eat it
r = fish_r;
c = fish_c;
t += min_dist;
sea[r][c] = 0;
eat++;
if(eat == size){
	size++;
	eat = 0;
}

 

전체 코드는 여기서 확인할 수 있다.