191009 백준 알고리즘 문제풀기

#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

struct shark {
	int x, y, size;
};

int map[22][22];
int check[22][22];

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

void init_check(int n)
{
	for (int j = 0; j < n; j++)
	{
		for (int i = 0; i < n; i++)
		{
			check[j][i] = 0;
		}
	}
}

void shark_grow(int &eat_cnt, shark &baby)
{
	if (eat_cnt == baby.size)
	{//만약 먹은량이 상어크기와 같다면
		baby.size++; // 상어 크기 키우고
		eat_cnt = 0; // 먹은량 초기화
	}
}

int main()
{
	int N;
	scanf("%d ", &N);
	shark baby;
	for (int j = 0; j < N; j++)
	{
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &map[j][i]);
			if (map[j][i] == 9)
			{
				baby.x = i;
				baby.y = j;
				baby.size = 2;
				map[j][i] = 0;
			}
		}
	}

	int answer = 0;
	bool flag = false;
	int eat_count = 0;
	int timer = 0;
	while (1)
	{
		//더 이상 먹을 고기 없는 경우 빠져나간다.
		if (flag) break;

		//check 맵 매 초마다 초기화
		init_check(N);

		//상어 현재 위치 check
		queue<pair<int, int>> q;

		int cx = baby.x;
		int cy = baby.y;
		
		check[cy][cx] = 1;
		q.push(make_pair(cx, cy));
		bool eat = false;
		
		int distance = 1000;
		int min_x = 1000;
		int min_y = 1000;

		while (!q.empty())
		{
			cx = q.front().first;
			cy = q.front().second;
			q.pop();
			for (int i = 0; i < 4; i++)
			{ //상어 다음 위치를 간다.
				int nx = cx + dx[i];
				int ny = cy + dy[i];
				if (0 <= nx && nx < N && 0 <= ny && ny < N&&check[ny][nx] == 0 && map[ny][nx] <= baby.size)
				{//맵 영역 안이고, 간 적이 없고, 맵 물고기 크기가 상어 이하라면 간다.
					//일단 방문한다.
					check[ny][nx] = check[cy][cx] + 1;
					q.push(make_pair(nx, ny));
					if (0 < map[ny][nx] && map[ny][nx] < baby.size)
					{//먹을 수 있는 물고기가 존재한다면
						eat = true; // 먹는다고 표시 하고
						if (check[ny][nx] < distance)
						{//만약 지금 방문한 위치가 가장 가깝다면
							min_x = nx; // 최소 위치 초기화
							min_y = ny;
							distance = check[ny][nx];
						}
						else if (check[ny][nx] == distance)
						{//만약 지금 방문한 거리가 가장 가까운 거리와 같다면
							int temp = min_x;
							if (ny < min_y)
							{ // 가장 위의 물고기를 먹고
								min_x = nx;
								min_y = ny;
								if (nx < temp)
								{ // 그중에서도 왼쪽 물고길 먹는다.
									min_x = nx;
									min_y = ny;
								}
							}
						}
					}					
				}
			}
		}
		if (eat)
		{//먹은 고기가 있다면
			eat_count++; // 먹는다.
			baby.x = min_x; // 상어 위치 초기화
			baby.y = min_y;
			map[min_y][min_x] = 0; //먹힌 물고기 지우기
			timer += check[min_y][min_x] - 1; // 먹는데 걸린 시간 더하기

			//상어를 조건에 맞게 키운다.
			shark_grow(eat_count, baby);
		}
		else flag = true; //맵에 먹을 고기 없으면 끝낸다.
	}
	printf("%d\n", timer);
  
	//std::system("pause");
	return 0;
}