🙇‍♀️라이언 킹 심바(삼성 SW역량평가 기출 : BFS활용)

N×N 크기의 정글에 토끼 M마리와 어린 사자 심바가 있다.

정글은 1×1 크기의 격자로 이루어져 있다.

각 격자칸에는 토끼 1한마리가 있거나 또는 없을 수 있다.

어린 사자 심바는 주어진 정글에서 토끼를 잡아먹고 덩치를 키워 삼촌 스카에게 복수를 하러 갈 예정이다.

어린 사자 심바와 토끼는 모두 몸 크기를 가지고 있고, 이 크기는 자연수이다.

가장 처음에 어린 사자 심바의 크기는 2이고, 심바는 1초에 인접한 상하좌우 격자칸으로 이동할 수 있다.

어린 사자 심바는 자신보다 크기가 큰 토끼가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다.

심바는 자신보다 크기가 작은 토끼만 잡아먹을 수 있다.

크기가 같은 토끼는 먹을 수는 없지만, 그 토끼가 있는 칸은 지날 수 있다.

어린 사자 심바가 토끼를 잡아먹기 위한 이동규칙은 다음과 같다.

1) 더 이상 먹을 수 있는 토끼가 정글에 없다면 이제 심바는 삼촌 스카에게 복수하러 갈 수 있다.
2) 먹을 수 있는 토끼가 딱 한마리라면, 그 토끼를 먹으러 간다.
3) 먹을 수 있는 토끼가 2마리 이상이면, 거리가 가장 가까운 토끼를 먹으러 간다.

① 거리는 심바가 있는 칸에서 먹으려고 하는 토끼가 있는 칸으로 이동할 때, 지나야하는 칸 의 개수의 최소값이다.
② 가장 가까운 토끼가 많으면, 그 중 가장 위쪽에 있는 토끼, 그러한 토끼가 여러 마리라면, 가장 왼쪽에 있는 토끼를 잡아먹는다.

심바가 격자칸 하나를 이동하는데 1초 걸리고, 토끼를 먹는데 걸리는 시간은 없다고 가정한다.

심바가 해당 격자칸의 토끼를 먹으면, 그 칸은 빈 칸이 된다.

심바는 자신의 몸 크기와 같은 마리수 만큼 잡아먹으면 몸의 크기가 1증가한다.

만약 심바의 몸크기가 5라면 자신보다 작은 토끼 5마리를 잡아먹으면 심바의 몸 크기는 6으로 변한다.

정글의 상태가 주어졌을 때, 심바가 몇 초 동안 토끼를 잡아먹고 삼촌 스카에게 복수를 하러 갈 수 있는지 구하는 프로그램을 작성하시오.

▣ 입력설명
첫 번째 줄에 정글의 크기 N(2 ≤ N ≤ 25)이 주어진다.

둘 번째 줄부터 정글의 지도 정보가 주어진다.

0은 빈칸이고, 각 토끼의 크기(1, 2, 3, 4, 5, 6, 7)과 9는 심바를 뜻한다.

▣ 출력설명
첫 번째 줄에 심바가 토끼를 잡아먹고 삼촌 스카에게 복수를 하러갈 수 있는 시간을 출력한다.

▣ 입력예제 1 
3
0 1 3
1 9 1
0 1 1

▣ 출력예제 1
10

🚀풀이

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int map[21][21], ch[21][21];
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
struct State {
	int x, y, dis;
	State(int a, int b, int c) {
		x = a;
		y = b;
		dis = c;
	}
	//	bool operator<(const State &bb)const{
	//		if(dis==bb.dis){
	//			if(x==bb.x) return y>bb.y;
	//			else return x>bb.x;
	//		}
	//		else return dis>bb.dis;
	//	}
	bool operator<(const State& b)const {
		if (dis != b.dis) return dis > b.dis;
		if (x != b.x) return x > b.x;
		else return y > b.y;
	}
};

struct Lion {
	int x, y, s, ate;
	void sizeUp() {
		ate = 0;
		s++;
	}
};

int main() {
	//freopen("input.txt", "rt", stdin);
	int n, i, j, res = 0;
	priority_queue<State> Q;
	Lion simba;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 9) {
				simba.x = i;
				simba.y = j;
				map[i][j] = 0;
			}
		}
	}
	Q.push(State(simba.x, simba.y, 0));
	simba.s = 2;
	simba.ate = 0;
	while (!Q.empty()) {
		State tmp = Q.top();
		Q.pop();
		int x = tmp.x;
		int y = tmp.y;
		int z = tmp.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 = tmp.dis;
		}
		for (i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx<1 || xx>n || yy<1 || yy>n || map[xx][yy] > simba.s || ch[xx][yy] > 0) continue;
			Q.push(State(xx, yy, z + 1));
			ch[xx][yy] = 1;
		}
	}
	printf("%d\n", res);
	return 0;
}

참고