lecture/algorithm - c++
[c++] 라이언킹 심바(BFS)
tonirr
2021. 1. 30. 20:01
#include <iostream>
#include <vector>
#include <stdlib.h>
#include <queue>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
int k, m, n, res=0, map[1010][1010], ch[1010][1010];
struct Loc {
int x, y, dis;
Loc(int a, int b, int c){
x = a;
y = b;
dis = c;
}
bool operator<(const Loc &bb) const{
if(dis==bb.dis){
if(x==bb.x) return y>bb.y;
else return x>bb.x;
}
else return dis>bb.dis;
}
};
struct Lion{
int x, y, s, ate;
void sizeUp(){
ate=0;
s++;
}
};
priority_queue<Loc> Q;
int main() {
int i, j;
Lion simba;
freopen("input.txt", "rt", stdin);
scanf("%d", &n);
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
scanf("%d", &map[i][j]);
if(map[i][j]==9){
Q.push(Loc(i, j, 0));
map[i][j]=0;
}
}
}
simba.s = 2;
simba.ate = 0;
while(!Q.empty()){
Loc loc =Q.top();
Q.pop();
int x = loc.x;
int y = loc.y;
int z = loc.dis;
if(map[x][y]!=0 && map[x][y]<simba.s){
simba.x=x;
simba.y=y;
simba.ate++;
if(simba.ate>=simba.s) simba.sizeUp();
map[x][y]=0;
for(i=1; i<=n; i++){
for(j=1; j<=n; j++){
ch[i][j]=0;
}
}
while(!Q.empty()) Q.pop();
res=loc.dis;
}
for(k=0; k<4; k++){
int xx = loc.x + dx[k];
int yy = loc.y + dy[k];
if(simba.s < map[xx][yy] || xx>n || xx<1 || yy>n || yy<1 || ch[xx][yy]>0) continue;
Q.push(Loc(xx, yy, z+1));
ch[xx][yy]=1;
}
}
printf("%d", res);
return 0;
}
어떻게 풀어야겠다는 방향은 잡았는데도 조건들을 하나씩 맞추다보니
쉽게 풀리지 않는 문제였다.
기존 BFS문제처럼 한번만 움직여서 체크하는 문제가 아니라
한번 움직여서 그 자리에 토끼가 없다면 움직인 자리에서 다시 상하좌우로 탐색하면서 그 자리에서 자리 탐색하는 방식으로 진행된다.
심바의 초기 위치는 9로 해당 위치에서 시작한다.
해당 위치에서 상하좌우로 탐색하면서 조건에 맞는지 확인하면서 체크배열 해당좌표의 값에 1로 체크를 해준다.
** 체크배열에 체크하는 조건
1. x,와 y좌표 모두 1보다 크고 n보다 작을 것
2. 심바의 크기가 map배열 (x, y)의 값보다 클 것
위의 조건에 해당 하는 ch배열 좌표값에 1로 체크하면서 우선순위 큐에 넣어준다.
큐에 좌표를 넣으면서 동시에 토끼가 움직이는 거리를 1씩 늘려가면서 값을 넣는다.
큐에 들어간 ch배열에 체크된 좌표들이 하나씩 나오면서 먹을 수 있는 토끼가 있는지 확인한다.
먹을 수 있는 토끼가 있다면
심바의 위치를 바꾸고
심바의 바뀐 위치를 map에서 해당좌표의 값을 0으로 만들고
ch배열의 값들을 모두 0으로 초기화하고 큐에서 모든 값들을 빼준다.
이런 과정을 통해 계속적으로 진행하면서 res값으로 시간을 출력해준다.