[c++] 라이언킹 심바(BFS)

#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값으로 시간을 출력해준다.