아기 상어
문제 해석
아기 상어가 몇초까지 물고기를 잡아먹을 수 있는 지 구하는 문제입니다.
초기 크기가 2인 아기상어는 자신보다 작거나 같은 물고기가 있는 곳에 도달할 수 있습니다.
가장 가까운 물고기를 잡아먹는데, 거리가 같은 물고기가 여러마리면, 가장 위, 가장 왼쪽에 위치한 물고기를 우선적으로 먹습니다.
자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1 증가합니다.
설계(10)
전형적인 BFS문제로 보입니다.
가장 가까운 물고기를 bfs로 찾은 후, 큐를 모두 비우고 다시 시작하는 방식으로 진행합니다.
처음에 이동방향을 우선순위가 큰 방향부터 움직여서 가장 가깝고 우선순위가 높은 물고기를 찾으려 했지만, 반례가 생기기 때문에 거리가 같은 물고기를 벡터에 저장하여 정렬하는 방식으로 변경하였습니다.
구현(15)
코드
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
#define MAXN 20
int N,cnt;
int s_size=2;
int arr[MAXN][MAXN];
bool visited[MAXN][MAXN];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
queue<pair<int,int> > q;
int bfs(){
int time = 0;
int res = 0;
while (!q.empty()){
time++;
int q_size = q.size();
vector<pair<int,int> > vt;
while (q_size--){
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k = 0; k<4; k++){
int nx = x + dx[k];
int ny = y + dy[k];
if (nx< 0 || ny < 0 || nx>=N || ny>=N) continue;
if (visited[nx][ny] || s_size<arr[nx][ny]) continue;
visited[nx][ny] = true;
q.push({nx,ny});
if (arr[nx][ny] && s_size > arr[nx][ny]){
vt.push_back({nx,ny});
}
}
}
if (vt.size()){
sort(vt.begin(),vt.end());
while (!q.empty()) q.pop();
memset(visited,false,sizeof(visited));
q.push(vt[0]);
visited[vt[0].first][vt[0].second] = true;
arr[vt[0].first][vt[0].second] = 0;
cnt++;
if (cnt== s_size) s_size++,cnt=0;
res += time;
time = 0;
}
}
return res;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N;
for (int i =0 ;i <N; i++){
for (int j= 0;j<N;j++){
cin >> arr[i][j];
if (arr[i][j] ==9){
q.push({i,j});
visited[i][j] = true;
arr[i][j] = 0;
}
}
}
cout << bfs() <<"\n";
return 0;
}
디버깅
물고기를 먹은 후, arr배열에서 해당 물고기를 지우지 않는 실수를 하였습니다.
time을 그냥 리턴하는 실수를 하였습니다.
위와 같이 그냥 리턴할 경우, 먹을 수 있는 마지막 물고기를 먹고 나서 다른 곳으로 이동하는 시간까지 포함하기 때문에 이런식으로 구현하면 안됩니다.
res변수를 추가하여, 물고기를 먹을 때마다 res+= time하고 time을 0으로 초기화하는 방식으로 변경하였습니다.
제출결과
0 ms
마무리
BFS를 이용하는 문제입니다. 이동 방향 별로 우선순위가 있기 때문에 이를 잘 생각해서 처리해야합니다.