(c++) 16236 아기상어🦈

16236 아기상어 🦈

https://www.acmicpc.net/problem/16236

개인적으로 많이 어려웠던 문제!
-> 알고보니 문제를 제대로 이해하지 못했던 문제..

• 현재 상어 위치에서부터 물고기의 거리를 구한다
  • 단, 상어보다 큰 물고기는 지나갈 수 없다.
• 가장 거리가 가까운 물고기들을 고른다.
  • 0보다 크고 상어의 크기보다는 작아야한다.
• 고른 물고기 중 가장 위쪽에 있는(같으면 왼쪽에 있는) 물고기를 골라서 먹는다.
  • 현재 상어의 위치는 0으로 하고 먹을 물고기의 위치에 상어(9)를 둔다.
  • 상어가 먹은 물고기 수를 증가시키고 만약 먹은 물고기 수가 상어의 크기와 같다면 상어의 크기를 증가시킨다.
  • 고른 물고기와 상어 사이의 거리만큼 시간을 증가시킨다.

나는 위 로직을 먹을 물고기가 없을때까지 반복시켜서 문제를 해결했다.

2%에서 자꾸 시간초과가 나서 왜인지 알아보니 상어크기가 9 이상이 되면 무한루프에 걸리는 것이었다. 그래서 76째 줄에 상어 크기가 7 이상 되지 않도록 추가했다.

---

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int N;
void initVisited(vector<vector<bool>> &visited) {
	visited.clear();
	for (int i = 0; i < N; i++) {
		vector<bool> tmp(N,false);
		visited.push_back(tmp);
	}
}

int main() {
	 cin >> N;
	vector<vector<int>> sea(N);
	pair<int, int> shark; //상어 위치
	for (int i = 0; i < N; i++) { //입력
		for (int k = 0; k < N; k++) {
			int input; cin >> input;
			sea[i].push_back(input);
			if (input == 9) {
				shark = { i,k };
			}
		}
	}
	int sharkSize = 2; //상어 크기
	int eated = 0; //먹은 물고기 수
	int totalTime = 0;
	int dx[] = { 0,1,0,-1 };
	int dy[] = { -1,0,1,0 };
	vector<vector<int>> canEat; //먹을 수 있는 물고기
	do {
		canEat.clear();
		int minDist = 5000; //canEat에 들어갈 수 있는 거리
		queue<vector<int>> q; //x,y,거리
		vector<vector<bool>> visited(N, vector<bool>(N, false));
		q.push({ shark.first,shark.second,0 });
		visited[shark.first][shark.second] = true;
		while (!q.empty()) {
			vector<int> now = q.front(); q.pop();
			if (now[2] > minDist) continue;
			if (0 < sea[now[0]][now[1]] && sea[now[0]][now[1]] < sharkSize) {
				if (now[2] < minDist) {
					minDist = now[2];
					canEat.clear();
					canEat.push_back(now);
				}
				else if (now[2] == minDist) {
					canEat.push_back(now);
				}
			}
			for (int i = 0; i < 4; i++) {
				int xx = now[0] + dx[i];
				int yy = now[1] + dy[i];
				if (0 <= xx && xx < N && 0 <= yy && yy < N && !visited[xx][yy]) {
					if (sea[xx][yy] <= sharkSize) {
						visited[xx][yy] = true;
						q.push({ xx,yy,now[2] + 1 });
					}
				}
			}
		}
		if (canEat.size() > 0) {
			sort(canEat.begin(), canEat.end());
			vector<int> togo = canEat[0];
			sea[shark.first][shark.second] = 0;
			sea[togo[0]][togo[1]] = 9;
			shark = { togo[0],togo[1] };
			totalTime += togo[2];
			eated++;
			if (eated == sharkSize) {
				sharkSize++;
				if (sharkSize >= 7) {
					sharkSize = 7;
				}
				eated = 0;
			}
		}
	} while (!canEat.empty());
	cout << totalTime << endl;
	return 0;
}

---