(c++)백준 16236번: 아기 상어

www.acmicpc.net/problem/16236

16236번: 아기 상어

[풀이]

bfs 최단거리를 구하는 문제였다.

 

1. 아기 상어의 크기보다 작은 물고기를 벡터에 저장

2. 먹을 수 있는 물고기 없으면 종료

3. 1마리면 그 자리까지 갈 수 있는지 확인 후 갈 수 있으면 먹는다. 갈 수 없으면 종료. (Time += 물고기 먹으러 간 거리)

4. 2마리 이상이면 그 자리까지 갈 수 있는지와 어느 물고기가 가장 가까운지 비교해가며 거리를 구한다. 어떤 물고기로도 갈 수 없으면 종료. (Time += 가장 가까운 물고기 먹으러 간 거리)

 

※ 이동하다가 다른 먹을 수 있는 물고기를 만났을 때 큐에 추가하지 않으면 시간 단축 가능!

 

#include <iostream>
#include <queue>
#include <cstring>//memset
using namespace std;

struct Pos {
	int x, y;
	int d;//거리
};

struct Fish {
	int x, y;
};

int N;
int Map[20][20];
bool visited[20][20];
vector<Fish>fish;//먹을 수 있는 물고기
const int dx[] = { -1,1,0,0 };//위,아래
const int dy[] = { 0,0,-1,1 };//왼,오
int sharkSize = 2;
int feedCnt = 0;
int fish_cnt;//먹을 수 있는 물고기 수
int sx, sy;//상어좌표
int Time = 0;

void checkFish() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (Map[i][j] != 0 && Map[i][j] < sharkSize)
				fish.push_back({ i,j });
		}
	}
}

int getDist(int destx, int desty) {
	memset(visited, false, sizeof(visited));
	queue<Pos>q;
	q.push({ sx,sy,0 });
	visited[sx][sy] = true;
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int d = q.front().d;
		q.pop();
		if (x == destx && y == desty) {
			return d;
		}
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N)
				continue;
			if (Map[nx][ny] > sharkSize)
				continue;
			//먹을 수 있는 다른 물고기 지나가는 경우 제외하면 시간 단축!
			if ((nx != destx && ny != desty) && Map[nx][ny] > 0 && Map[nx][ny] < sharkSize)
				continue;
			if (visited[nx][ny] == false) {
				visited[nx][ny] = true;
				q.push({ nx,ny,d+1 });
			}
		}
	}
	return -1;
}

void solution() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> Map[i][j];
			if (Map[i][j] == 9) {
				Map[i][j] = 0;
				sx = i;
				sy = j;
			}
		}
	}
	
	while (1) {
		//먹을 수 있는 물고기 확인
		checkFish();
		fish_cnt = fish.size();
		//cout << fish_cnt << '\n';
		if (fish_cnt == 0)
			break;
		//물고기 한 마리면
		if (fish_cnt == 1) {
			int dist = getDist(fish[0].x, fish[0].y);
			//물고기를 먹을 수 없으면
			if (dist == -1)
				break;
			Time += dist;
			sx = fish[0].x;
			sy = fish[0].y;
			Map[sx][sy] = 0;
			feedCnt++;
		}
		else if(fish_cnt >= 2) {
			int Min = 987654321;
			int fx;
			int fy;
			bool flag = false;
			for (int i = 0; i < fish_cnt; i++) {
				int dist = getDist(fish[i].x, fish[i].y);
				//물고기를 먹을 수 없으면
				if (dist == -1)
					continue;
				if (dist < Min) {
					flag = true;
					Min = dist;
					fx = fish[i].x;
					fy = fish[i].y;
				}
				else if (dist == Min) {
					if (fx == fish[i].x) {
						if (fish[i].y < fy)
							fy = fish[i].y;
					}
					else if (fish[i].x < fx) {
						fx = fish[i].x;
						fy = fish[i].y;
					}
				}
			}
			//아무 물고기도 먹을 수 없으면
			if (flag == false)
				break;
			sx = fx;
			sy = fy;
			Map[sx][sy] = 0;
			Time += Min;
			feedCnt++;
		}
		if (sharkSize == feedCnt) {
			sharkSize++;
			feedCnt = 0;
		}
		fish.clear();
	}
	cout << Time << '\n';
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solution();
	return 0;
}