https://www.acmicpc.net/problem/16236
[문제 요약]
N x N 크기의 공간에 아기상어 한 마리와 1~6의 크기를 가진 물고기들이 있다.
아기상어의 초기 크기는 2이고, 자신의 크기와 같은 수의 물고기를 먹으면 크기가 1 증가한다.
아기상어는 1초에 한 칸씩 이동하면서 물고기를 먹고, 이동 시 다음과 같은 규칙을 따른다.
- 빈칸: 자유롭게 움직일 수 있다.
- 자신보다 작은 물고기: 먹을 수 있다.
- 자신과 크기가 같은 물고기: 먹을 수는 없지만, 그 물고기가 있는 칸을 지나갈 수는 있다.
- 자신보다 큰 물고기: 그 물고기가 있는 칸을 지나갈 수 없다.
또한 최대한 가까운 거리에 있는 먹을 수 있는 물고기를 먹어야 하고, 그러한 물고기가 여러마리일 경우 가장 위쪽에 있는 물고기를, 높이도 같다면 가장 왼쪽에 있는 물고기를 먹는다.
아기상어가 더 이상 먹을 수 있는 모든 물고기를 먹을 때 까지 걸린 시간을 출력한다.
[문제 풀이]
아기상어의 위치를 기준으로 가까운 지점부터 탐색을 해야 하므로, BFS를 통해 탐색한다.
이때 먹을 물고기의 우선순위가 거리 -> 세로위치 -> 가로위치 순으로 정해지므로 queue 대신 priority_queue를 사용한다.
(그냥 queue를 사용할 경우 먹어야 하는 물고기의 우선순위를 확인하는 것이 힘들다)
좌표의 거리, 세로위치, 가로위치 정보를 담은 구조체를 priority_queue 에 넣었다.
// 좌표 정보를 담는 구조체
// 거리, 세로위치, 가로위치를 순으로 정렬
struct Coord {
int n, m, dist;
// 구조체 생성자
Coord(int a, int b, int c) : n(a), m(b), dist(c) {}
// bool 연산자 오버로딩
bool operator<(const Coord x) const{
if(this->dist != x.dist) return this->dist > x.dist;
else if(this->n != x.n) return this->n > x.n;
else if(this->m != x.m) return this->m > x.m;
}
};
priority_queue<Coord> pq; // 이동할 수 있는 좌표
priority_queue<Coord> fish; //먹을 수 있는 뭃고기의 좌표
priority_queue 같은 경우 push 된 값들이 크기가 큰 순서부터 자동으로 정렬이 된다. 하지만 우리는 단순한 int 값이 아닌 구조체를 사용하고 있고, 우선순위가 특별한 방식으로 정해지므로 '<' 연산자를 오버로딩 사용한다.
위 코드와 같이 연산자 오버로딩을 할 경우 거리가 작을수록, 세로 좌표값이 작을수록, 가로 좌표값이 작을수록 '큰' 구조체로 연산이 되므로, pq.top()에는 가장 우선순위가 높은 좌표가, fish.top() 에는 우리가 먹어야 하는 물고기의 좌표가 위치하게 된다!
<BFS 구현>
// 이동할 수 있는 위치를 탐색
void bfs(){
int dd=pq.top().dist;
// dd+1 만큼의 거리를 이동해 갈 수 있는 모든 점을 enqueue
while(pq.top().dist==dd){
int n=pq.top().n;
int m=pq.top().m;
int dist=pq.top().dist;
pq.pop();
if(n>0 && sea[n-1][m]<=shark && !check[n-1][m]){
check[n-1][m]=true;
pq.push(Coord(n-1, m, dist+1));
if(sea[n-1][m]>0 && sea[n-1][m]<shark) fish.push(Coord(n-1, m, dist+1));
}
if(m>0 && sea[n][m-1]<=shark && !check[n][m-1]){
check[n][m-1]=true;
pq.push(Coord(n, m-1, dist+1));
if(sea[n][m-1]>0 && sea[n][m-1]<shark) fish.push(Coord(n, m-1, dist+1));
}
if(m<N-1 && sea[n][m+1]<=shark && !check[n][m+1]){
check[n][m+1]=true;
pq.push(Coord(n, m+1, dist+1));
if(sea[n][m+1]>0 && sea[n][m+1]<shark) fish.push(Coord(n, m+1, dist+1));
}
if(n<N-1 && sea[n+1][m]<=shark && !check[n+1][m]){
check[n+1][m]=true;
pq.push(Coord(n+1, m, dist+1));
if(sea[n+1][m]>0 && sea[n+1][m]<shark) fish.push(Coord(n+1, m, dist+1));
}
if(pq.empty()) break;
}
// 더 이상 이동할 좌표가 없는 경우, 탐색이 끝남
if(pq.empty()){
yumm=true;
return;
}
// 우선순위가 가장 높은 물고기를 먹음
if(!fish.empty()) eat(fish.top().n, fish.top().m, fish.top().dist);
}
pq 에는 상어가 위치할 수 있는 좌표들의 정보가 들어있다.
- 초기: 상어의 위치 정보만 들어있다.
- BFS 한 번 실행한 후: 초기 위치에서 거리 1만큼 이동했을 때의 위치 정보들이 들어있다.
- BFS n번 실행한 후: 초기 위치에서 거리 n만큼 이동했을 때의 위치 정보들이 들어있다.
거리가 n인 좌표들의 위, 왼쪽, 오른쪽, 아래를 탐색하며 상어가 이동할 수 있는지, 이미 방문한 위치는 아닌지 판단한 후 이동할 수 있다면 그 정보를 pq에 push 한다. 만약 먹을 수 있는 물고기도 위치해 있다면 fish 에도 push 한다.
n번째 BFS 호출에서 거리가 n-1 인 점들이 전부 dequeue 되고 거리가 n인 점들만 남을 때까지 이 작업을 반복한다. 이후 먹을 수 있는 물고기가 있다면 가장 우선순위가 높은 물고기인 fish.top()을 먹고, 더 이상 이동할 수 있는 좌표가 없다면 탐색을 종료한다. 물고기를 먹은 뒤에는 다시 pq에 상어의 위치만이 들어있게 된다.
[전체 코드]
#include <iostream>
#include <queue>
#include <functional>
using namespace std;
// 좌표 정보를 담는 구조체
// 거리, 세로위치, 가로위치를 순으로 정렬
struct Coord {
int n, m, dist;
Coord(int a, int b, int c) : n(a), m(b), dist(c) {}
bool operator<(const Coord x) const{
if(this->dist != x.dist) return this->dist > x.dist;
else if(this->n != x.n) return this->n > x.n;
else if(this->m != x.m) return this->m > x.m;
}
};
int N, sea[21][21], shark_n, shark_m, shark=2, cnt, ans;
bool check[21][21], yumm=false;
priority_queue<Coord> pq; // 이동할 수 있는 좌표
priority_queue<Coord> fish; //먹을 수 있는 뭃고기의 좌표
void eat(int i, int j, int d){
ans+=d;
sea[i][j]=0;
while (!pq.empty()) pq.pop();
while (!fish.empty()) fish.pop();
pq.push(Coord(i, j, 0));
cnt++;
if(cnt==shark){
cnt=0;
shark++;
}
for(int k=0; k<N; k++){
for(int p=0; p<N; p++){
check[k][p]=false;
}
}
check[i][j]=true;
}
// 이동할 수 있는 위치를 탐색
void bfs(){
int dd=pq.top().dist;
// dd+1 만큼의 거리를 이동해 갈 수 있는 모든 점을 enqueue
while(pq.top().dist==dd){
int n=pq.top().n;
int m=pq.top().m;
int dist=pq.top().dist;
pq.pop();
if(n>0 && sea[n-1][m]<=shark && !check[n-1][m]){
check[n-1][m]=true;
pq.push(Coord(n-1, m, dist+1));
if(sea[n-1][m]>0 && sea[n-1][m]<shark) fish.push(Coord(n-1, m, dist+1));
}
if(m>0 && sea[n][m-1]<=shark && !check[n][m-1]){
check[n][m-1]=true;
pq.push(Coord(n, m-1, dist+1));
if(sea[n][m-1]>0 && sea[n][m-1]<shark) fish.push(Coord(n, m-1, dist+1));
}
if(m<N-1 && sea[n][m+1]<=shark && !check[n][m+1]){
check[n][m+1]=true;
pq.push(Coord(n, m+1, dist+1));
if(sea[n][m+1]>0 && sea[n][m+1]<shark) fish.push(Coord(n, m+1, dist+1));
}
if(n<N-1 && sea[n+1][m]<=shark && !check[n+1][m]){
check[n+1][m]=true;
pq.push(Coord(n+1, m, dist+1));
if(sea[n+1][m]>0 && sea[n+1][m]<shark) fish.push(Coord(n+1, m, dist+1));
}
if(pq.empty()) break;
}
// 더 이상 이동할 좌표가 없는 경우, 탐색이 끝남
if(pq.empty()){
yumm=true;
return;
}
// 우선순위가 가장 높은 물고기를 먹음
if(!fish.empty()) eat(fish.top().n, fish.top().m, fish.top().dist);
}
int main(){
cin>>N;
for(int i=0; i<N; i++){
for(int j=0; j<N; j++){
cin>>sea[i][j];
if(sea[i][j]==9){
shark_n=i;
shark_m=j;
sea[i][j]=0;
}
check[i][j]=false;
}
}
check[shark_n][shark_m] = true;
pq.push(Coord(shark_n, shark_m, 0));
while(1){
bfs();
if(yumm) break;
}
cout<<ans;
}
[주의할 점]
- 입력을 받은 후 상어의 위치를 빈칸으로 취급하도록 초기화 했는지 확인한다. 처음 입력을 받을 때 상어가 있던 위치를 이동할 수 없는 점으로 설정해버리는 불상사가 일어날 수 있다..
- bfs를 실행할 때 이미 방문한 점을 check 하지 않고 계속해서 방문하고 있지는 않은지 확인한다.
- 단순히 위, 왼, 오, 아래 순으로 queue에 푸쉬 하는 것으로는 좌표들의 우선순위대로 정렬이 되지 않는다. 이러한 방법을 사용할 경우 예제 4번의 값이 56이 나올 것이다.
- 같은 거리로 이동할 수 있는 모든 점을 탐색하기 전 까지는 물고기를 먹어서는 안 된다. 우선순위를 비교했을 때 "n의 거리에 있는 좌표들 중 우선순위가 높은 좌표에서 이동해 발견한 n+1 거리의 물고기" > "n의 거리에 있는 좌표들 중 우선순위가 밀리는 좌표에서 이동해 발견한 n+1 거리의 물고기" 일 것이란 보장을 할 수 없다. 이 점을 놓친 경우에도 예제 4번이 틀릴 것이다.
군대에서 처음으로 써보는 알고리즘 리뷰 글이었다. 앞으로 자주 써보도록 해야겠다!
연산자 오버로딩과 BFS를 연습하기 좋은 문제였다. 처음에 queue로 계속 시도하느라 고난이 많았다 ㅠㅠ
'알고리즘' 카테고리의 다른 글
| [BOJ #1655] 가운데를 말해요, C++ (8) | 2025.01.08 |
|---|---|
| [BOJ #5373] 큐빙(반례 포함), C++ (8) | 2025.01.04 |