[백준 16236번 - 아기상어] C++ 풀이

16236번.

 

나에게 생각보다 매우 많이 걸렸던 문제이다.

처음부터 다시짜고 다시짜고..를 한 5번 정도 했던 것 같았다.

 

우선, 처음에는 bfs 함수를 한번만 호출하여 한번에, 아기 상어가 잡아먹는 물고기들을 순서대로 queue에 담음과 동시에 distance 를 계산하여 answer를 구하려고 했다. 이건 매우 잘못된 접근이었다... 왜냐면 queue에 담을 아기상어를 찾는 것을 거리가 1, 2, 3, ... 이렇게 늘려가면서 위에서 아래로/왼쪽에서 오른쪽으로 훑어가면서 스캔하는 방식으로 for문을 돌리고, 잡아먹은 물고기 갯수를 ++하여 fish size도 늘려주도록 하였지만, 이렇게 하면 못 지나가는 곳의 물고기까지 먹을 수 있고/거리도 틀리다 (자기보다 큰 물고기는 못 지나가기 때문)

 

아 멀리를 이리저리 돌리다가 bfs한번으로는 도저히 방법을 생각 해 낼수 없었다.. 결국은 bfs를 한번 호출할 때마다, 최소 거리에 놓여있는 먹을 수 있는 물고기를 찾는 방식으로 바꿨다. 그리고 해당 위치를 중심 지점으로 바꾸고 다시 bfs를 돌린다. 아기 상어 위치가 바뀜에따라 최소 거리가 바뀌기 때문에 계속 check배열을 갱신해주어야 한다. 나는 해당 배열을 기준점에서의 거리로 세팅해주었고, 만약 먹을 수 있는 물고기라면 -1을 곱해주었다. 그래서 bfs 호출 후, 최소 거리이면서, 음수라면 해당 위치의 물고기를 먹을 수 있도록 하였다. check배열은 다시 초기화해주어야 한다. 만약 bfs를 돌았는데도, 먹을 수 있는 물고기 갯수가 0이라면, 종료하는것으로 했다.

 

#include <stdio.h>
#include <vector>
#include <queue>
#include <math.h>

using namespace std;

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

int n, m;
vector<vector<int>> v;
vector<vector<int>> visited; // 거리 담는다.
int fsize = 2;
int fish = 0;
int ans = 0;
int eat_cnt = 0;

struct coor{
	int x;
	int y;
	int cnt;
};

int minDist = 987654321;

void bfs(int x, int y) {
	minDist = 987654321;
	queue<coor> q;
	q.push({x, y, 1});
	while(!q.empty()) {
		int dist = q.front().cnt;
		int cx = q.front().x;
		int cy = q.front().y;
		visited[cx][cy] = dist;
		q.pop();
		for(int i = 0; i < 4; ++i) {
			int nx = cx + dx[i];
			int ny = cy + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny] || v[nx][ny] > fsize) {
				continue;
			} else if (v[nx][ny] != 0 && v[nx][ny] < fsize) {
				// 먹을 수 있는 물고기
				if (v[nx][ny] > 0)
					v[nx][ny] *= -1;
				if(minDist > dist + 1)
					minDist = dist + 1;
				fish++;
				q.push({nx, ny, dist + 1});
				visited[nx][ny] = dist + 1;
			} else if (v[nx][ny] == 0 || v[nx][ny] == fsize) {
				// 지나만 갈 수 있는 곳
				q.push({nx, ny, dist + 1});
				visited[nx][ny] = dist + 1;
			}
		}
	}
}

int main() {
	scanf("%d", &n);
	v.assign(n + 1, vector<int>(n + 1, 0));
	visited.assign(n + 1, vector<int>(n + 1, 0));

	int start_x, start_y;

	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			scanf("%d", &v[i][j]);
			if (v[i][j] == 9) {
				start_x = i;
				start_y = j;
				v[i][j] = 0;
			}
		}
	}

	int fflag = 0;

	while(true) {
		visited[start_x][start_y] = 1;
		bfs(start_x, start_y);
		if (fish == 0)
			break;
		for(int i = 0; i < n; ++i) {
			for(int j = 0; j < n; ++j) {
				if (visited[i][j] == minDist && v[i][j] < 0) {
					start_x = i;
					start_y = j;

					v[i][j] = 0;
					ans += minDist - 1;
					fflag = 1;

					eat_cnt += 1;
					if (eat_cnt == fsize) {
						eat_cnt = 0;
						fsize++;
					}
					break;
				}
			}
			if (fflag == 1)
				break;
		}
		fflag = 0;
		fish = 0;
		visited.assign(n + 1, vector<int>(n + 1, 0));
	}
	printf("%d\n", ans);
	return 0;
}