백준 16236번 아기 상어 (C++)

 예전엔 못풀었는데 드디어 풀었다!

이 문제는 BFS인데도 각 노드(칸)에서 따져줘야할 것이 많고 그저 먹이까지의 최소거리가 아닌 중간에 이동할 수 없는 칸도 존재하고 게다가 먹이들한테는 우선순위까지 있다..

내 풀이는 이렇다.

 

1. 현재 지점에서 bfs 하며 먹을 수 있는 칸의 거리와 좌표를 모아 벡터에 담는다.

2. 모은 벡터를 거리가 짧은 순, 가장 위에 있으며 가장 왼쪽에 있는 순서대로 정렬한다. comp를 직접 만들어서 쓰면 된다.

3. 이후 먹을수있는 칸에서 다시 bfs를 시도한다.

 

내 코드는 bfs임에도 재귀의 성질을 갖고 있다. 매우 거부감 들었지만 size가 20x20이라 통과한 건가 싶다.. 속도가 다른 코드들에 비해 좀 느린편이다.

 

#include <iostream>
#include <queue>
#include <algorithm>
#include <cmath>
#define MAX 21
using namespace std;
int sea[MAX][MAX] = { 0, };
int N;
int LV = 2;
int eat = 0;
int len = 0;

int dx[] = { 1,0,-1,0 };
int dy[] = { 0,-1,0,1 };

bool comp(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) { // 
	if (a.first < b.first) {
		return true;
	}
	else if (a.first == b.first) {
		if (a.second.first < b.second.first) {
			return true;
		}
		else if (a.second.first == b.second.first) {
			if (a.second.second < b.second.second) {
				return true;
			}
			else
				return false;
		}
		else
			return false;
	}
	else 
		return false;
}


void bfs(int x, int y) {
	int dis[MAX][MAX] = { 0, };
	bool visited[MAX][MAX] = { false, };
	vector<pair<int, pair<int, int>>> vec;
	visited[x][y] = true;
	queue<pair<int, int>> Q;
	Q.push(make_pair(x, y));
	while (!Q.empty()) {
		int X = Q.front().first;
		int Y = Q.front().second;
		Q.pop();
		
		if (sea[X][Y] < LV && sea[X][Y] != 0) {
			vec.push_back(make_pair(dis[X][Y], make_pair(X, Y)));	
		}
		for (int i = 0; i < 4; i++) {
			int NX = X + dx[i];
			int NY = Y + dy[i];
			if (NX < N && NX > -1 && NY < N && NY > -1 && visited[NX][NY] == false && sea[NX][NY] <= LV) {
				Q.push(make_pair(NX, NY));
				dis[NX][NY] = dis[X][Y] + 1;
				visited[NX][NY] = true;
			}
		}
	}
	if (!vec.empty()) {
		sort(vec.begin(), vec.end(), comp);
		eat++;
		if (LV == eat) {
			LV++;
			eat = 0;
		}
		sea[vec[0].second.first][vec[0].second.second] = 0;
		len += vec[0].first;
		bfs(vec[0].second.first, vec[0].second.second);
        return;
	}
}
int main() {
	int x, y;
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> sea[i][j];
			if (sea[i][j] == 9) {
				x = i;
				y = j;
			}
		}
	}
	sea[x][y] = 0;
	bfs(x, y);
	cout << len << endl;
}

 

속도를 좀 개선해보려 했지만 실패했다.