대엉코딩

www.acmicpc.net/problem/16236

1. 풀이방법

- BFS 문제. DFS로도 풀어보았지만 로직은 맞는 것 같지만 역시나 시간 초과가 나옵니다. (코드는 첨부)

- 상어의 위치로 부터 조건에 가장 부합하는 물고기 위치를 BFS로 탐색해 찾아낸 다음

- 그 위치의 물고기를 먹고 상어의크기를 조정이 필요할 경우 해주고 그 위치로 아기상어를 옮겨 주시면 됩니다.

- 저는 DFS를 먼저 풀고 거기서 재활용할 함수들은 재활용하고 makefishcase만 bfs로 바꿔서 구현하여서,

- 불필요한 부분도 들어있습니다. 깔끔하지 않습니다.

2. 주의사항

- 한가지 있는데, 저와 같은 케이스인 분들을 위해 기록합니다.

- bfs로 짰는데 "시간초과" 라는 결과를 얻었습니다.

- 코드를 아무리 봐도 시간초과가 나올만한 연산을 하는 곳이 없습니다.

- 이럴경우 거의 십중팔구 무한루프에 빠지는 테스트케이스가 존재한다는 뜻입니다.

- 그것을 곰곰히 생각해보니, 

- 이러한 경우 입니다

  9 0 0

  4 4 4

  0 0 1

-저의 코드에서는 전체 바다에서 먹을 수 있는 물고기가 존재하는지 체크하는 함수가 있는데,

- 그 함수는 이러한 케이스에서 1이라는 물고기가 있으므로 break;를 걸지 않아서 무한루프에 빠져

- 시간초과가 나오는 것이였습니다.

- 물론 종료조건 함수를 훨씬 정교하고 예쁘게 만드셨다면 해당되지 않으실 수 도 있습니다!

3. 나의코드

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

int dx[4] = { 1,-1,0,0 }; //상하좌우 4방향 탐색
int dy[4] = { 0,0,-1,1 };
int sea[21][21];
bool visit[21][21];
int N;
int resultsecond;
int tmpeat = 0;
int sharksize = 2;
int sharkx, sharky;
int failsecond = -1;

struct fish {
	int x, y, far;
};
vector<fish> farr;
void inputs() {
	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) { sharkx = i; sharky = j; }
		}
	}
}
bool checksea() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (sea[i][j] > 0 && sea[i][j] < sharksize && sea[i][j] != 9) { return false; }
		}
	}
	return true; //더이상 잡아 먹을 것 이 없음
}
void visitclear() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visit[i][j] = false;
		}
	}
}
queue<fish> tmpq;
void makefishcase(int x, int y) {
	tmpq.push({ x,y,0 });
	int cnt = 0;
	while (1) {
		int si = tmpq.size();
		if (si == 0) { failsecond = resultsecond; break; }
		while (si--) {
			int tx = tmpq.front().x;
			int ty = tmpq.front().y;
			tmpq.pop();
			if (sea[tx][ty] > 0 && sea[tx][ty] < sharksize && sea[tx][ty] != 9) {
				farr.push_back({ tx,ty,cnt });
			}
			for (int i = 0; i < 4; i++) {
				int nextx = tx + dx[i]; int nexty = ty + dy[i];
				if (nextx >= 0 && nextx < N && nexty >= 0 && nexty < N) {
					if (visit[nextx][nexty] == false && sea[nextx][nexty] <= sharksize) {
						visit[nextx][nexty] = true; 
						tmpq.push({ nextx,nexty,0 }); 
					}
				}
			}
		}
		if (farr.empty() == false) break;
		cnt++;
	}
}
bool compare(fish& lh, fish& rh) {
	if (lh.far < rh.far) return true;
	else if (lh.far == rh.far) {
		if (lh.x < rh.x) return true;
		else if (lh.x == rh.x) {
			if (lh.y < rh.y) return true;
			else return false;
		}
		else return false;
	}
	else return false;
}
void queuereset() {
	while (!tmpq.empty()) {
		tmpq.pop();
	}
}
void eatfish() {
	queuereset();
	makefishcase(sharkx, sharky);
	if (failsecond != -1) return;
	sort(farr.begin(), farr.end(), compare); //거리 순 > 위에있는순> 왼쪽에 있는순으로 소팅
	sea[sharkx][sharky] = 0;
	sharkx = farr[0].x; sharky = farr[0].y;
	tmpeat++;
	if (sharksize == tmpeat) {
		tmpeat = 0; sharksize++;
	}
	sea[sharkx][sharky] = 9;
	resultsecond += farr[0].far;
	visitclear();
	farr.clear();
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	while (1) {
		if (checksea()) break;
		visit[sharkx][sharky] = true;
		eatfish();
		if (failsecond != -1) break;
	}
	if (failsecond == -1) {
		cout << resultsecond << "\n";
	}
	else { cout << failsecond << "\n"; }
	return 0;
}