백준 / BOJ / 16236 아기상어 C++

www.acmicpc.net/problem/16236

16236번: 아기 상어

삼성 SW 기출문제로도 유명한 아기 상어 문제입니다. 상어 위치로부터 문제로부터 요구하는 물고기의 위치까지 최단 거리를 구하여 계속 더하면 되므로 bfs를 사용하였습니다. 

 

처음에는 상어의 현재 위치에서 $n^2$개 중 먹을 수 있는 물고기를 체크하고, 이 물고기들을 bfs를 이용하여 최단 거리와 어떤 물고기를 먹을 지 구한 뒤 while문으로 동일하게 반복하였습니다. 그러니 $O(n^6)$이 되어 시간초과가 떴습니다. (bfs : $O(n^2)$, while : $O(n^2)$)

 

시간을 줄이기 위해 $n^2$ 중 먹을 수 있는 물고기를 체크하는 과정 없이 bfs를 이용하여 먹어야하는 물고기의 좌표와 check배열을 이용하여 해당 좌표까지의 거리를 구하였습니다.

그리하여 $O(n^4)$ 으로 해결할 수 있습니다.

 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>

using namespace std;

int n;
int Map[21][21];
pair<pair<int, int>,int>shark;
int dy[4] = { 0,0,-1,1 };
int dx[4] = { 1,-1,0,0 };

int dist = 987654321;
int eat_x = 0;
int eat_y = 0;
int check[21][21];

void make_map()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> Map[i][j];
			if (Map[i][j] == 9) {
				shark.first = { i,j };
				shark.second = 2;
			}
			check[i][j] = -1;
		}
	}
}

void bfs(pair<pair<int,int>,int>S)
{
	int w = S.second;
	int Y = S.first.first;
	int X = S.first.second;
	check[Y][X] = 0;

	queue<pair<int, int>>q;
	q.push({ Y,X });

	while (!q.empty())
	{
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny >= 1 && ny <= n && nx >= 1 && nx <= n)
			{
				if (check[ny][nx] != -1 || Map[ny][nx] > w) {
					continue;
				}

				check[ny][nx] = check[y][x] + 1;

				if (Map[ny][nx] > 0 && Map[ny][nx] < w) {
					if (dist > check[ny][nx]) {
						eat_y = ny;
						eat_x = nx;
						dist = check[ny][nx];
					}

					else {
						if (dist == check[ny][nx]) {
							if (eat_y == ny) {
								if (eat_x > nx) {
									eat_x = nx;
								}
							}
							else if (eat_y > ny) {
								eat_y = ny;
								eat_x = nx;
							}
						}
					}
				}
				q.push({ ny,nx });
			}
		}
	}
}

int solve()
{
	int time = 0;
	int cnt = 0;
	
	while (1)
	{
		memset(check, -1, sizeof(check));
		eat_x = 0;
		eat_y = 0;
		dist = 987654321;

		bfs(shark);

		if (eat_x == 0 && eat_y == 0)
			break;

		time += check[eat_y][eat_x];
		cnt++;
		Map[eat_y][eat_x] = 9;
		Map[shark.first.first][shark.first.second] = 0;
		shark.first = { eat_y,eat_x };

		if (cnt == shark.second) {
			cnt = 0;
			shark.second++;
		}
	}

	return time;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	make_map();
	int answer = solve();
	cout << answer;
}