16236 아기상어

문제링크

코드 설명

처음에는 우선순위 큐로 접근하였지만 좀더 구현스럽게 바꿔풀었다(우선순위큐로도 풀이가능)

하지만 직접 다음 먹으러가는 물고기 find_fish() 함수와
상어보다 작은 물고기가 존재하는지 check_fish()함수로 나눠서 풀었을때

**찾지 못할경우 + 자기보다 큰 물고기들에게 둘러쌓일 예외 case를 항상 생각하자 (return -1)
또한 예외 종료 조건 및 탈출조건도 ..

if (fish.size() == 0 || Time==987654321) {
cout << answer;
break;
}

마지막으로 문제에서 배열을 0부터 세는지 1부터 세는지 부터 제일먼저 확인해서
map조건도 제대로 써주자

(if (ny<0 || nx <0 || ny>N-1 || nx > N-1) continue;)

코드

#include<iostream>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
int N;
int map[21][21];
bool visited[21][21];
int start_y, start_x;
struct FISH {
	int y;
	int x;
	int cost;
};

int fishSize = 2;
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,1,-1 };
int Num;
int Time;
int dist;
int answer;
vector<pair<int,int>> fish;
int bfs(int desty,int destx) { //물고기먹이까지의 시간(거리)
	memset(visited, false, sizeof(visited));
	queue<FISH> q;
	q.push({ start_y,start_x,0 });
	visited[start_y][start_x] = true;

	while (!q.empty()) {
		int y = q.front().y;
		int x = q.front().x;
		int cost = q.front().cost;
		q.pop();
		if (y == desty && x == destx) {
		
			return cost;
		}

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny<0 || nx <0 || ny>N-1 || nx > N-1) continue;
			if (map[ny][nx] > fishSize) continue; //물고기가 더크면 못지나가지만 같은크기면 지나갈수있음, 즉 q에 들어가도된다.
			if (!visited[ny][nx]) {
				q.push({ ny,nx,cost + 1 });
				visited[ny][nx] = true;

			}
		}


	}
	return -1;//목적지까지 갈수없음




}
void find_fish() { //조건에 맞는 물고기고르기
	Time = 987654321;
	int d = 0;
	
	for (int i = 0; i < fish.size(); i++) {
		

		d=bfs(fish[i].first, fish[i].second);
		if (d == -1) continue;
		if (Time > d) {
			Time = d;
			Num = i;
		}
		else if (Time == d) {
			if (fish[Num].first > fish[i].first) {
				Num = i;
				Time = d;
			}
			else if (fish[Num].first == fish[i].first) {
				if (fish[Num].second > fish[i].second) {
					Num = i;
					Time = d;
				}
			}
		}

	}

	
}
void check_fish() {
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			if (map[y][x] != 0 && map[y][x] != 9 && map[y][x] < fishSize) { //먹으러갈 물고기를 담는다.자기보다 작은물고기만 먹을수있다.
				fish.push_back({ y,x });
			}
		}
	}

}
int main() {
	cin >> N;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			cin >> map[y][x];
			if (map[y][x] == 9) {
				start_y = y;
				start_x = x;
				map[y][x] = 0;
			}
			
		}
	}
	int a = 0;
	
	while (1) {
		check_fish();
		find_fish();
		if (fish.size() == 0 || Time==987654321) { //예외 종료조건 생각해주자...미리 생각안해서 시간 소요 많이함(물고기가 더이상 없거나, 큰 물고기에 가로막힌경우)
			cout << answer;
			break;
		}
		
		answer += Time;
		
		//먹은곳 map 0으로 바꿔주고 bfs 시작 인덱스 변경
		map[fish[Num].first][fish[Num].second] = 0;
		start_y = fish[Num].first;
		start_x = fish[Num].second;
		
		a++;
		//상어크기
		if (a == fishSize) {
			fishSize++;
			a = 0;
		}
		fish.clear();


	}



	return 0;
}