[백준][16236번] 아기 상어

https://www.acmicpc.net/problem/16236

16236번: 아기 상어

 

풀이과정

1. 자신보다 작은 물고기를 찾아서 점점 덩치를 키워가는 문제이다. 먹을 수 있는 물고기 중 가장 가까운 거리에 위치한 물고기를 향한다. 현재 위치에서 가장 가까운 위치를 찾아야하기 때문에 bfs를 이용했다.

 

2. 아기 상어보다 크면 지나가지 못하는 조건과 자신과 같은 크기라면 먹을 수 없는 조건을 생각해야한다. 또 한 가장 가까운 위치에 존재하는 물고기의 수가 1개 이상 일 경우 가장 위쪽이면서 왼쪽인 물고기를 먹는다.

 

소스코드

#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
using namespace std;
int map[20][20];
int visited[20][20];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1,-1, 0, 0 };
int N, answer;
struct shark {
	int x;
	int y;
	int size;
	int level; //상어의 크기
}typedef shark;
shark g_shark;
int moveShark()
{
	memset(visited, 0, sizeof(visited));
	queue<pair<int, int>> que;
	vector<pair<int, int>> check;
	que.push(make_pair(g_shark.x, g_shark.y));
	int depth = 0;
	int findFish = 0;
	while (!que.empty()) {
		int queSize = que.size();
		depth++;
		for (int i = 0; i < queSize; i++) {
			pair<int, int> p = que.front(); que.pop();
			for (int j = 0; j < 4; j++) {
				int nx = p.first + dx[j];
				int ny = p.second + dy[j];
				if (nx < 0 || ny < 0 || nx >= N || ny >= N || map[ny][nx] > g_shark.level || visited[ny][nx] == 1) continue;
				visited[ny][nx] = 1;
				if (map[ny][nx] == 0 || map[ny][nx] == g_shark.level) {
					que.push(make_pair(nx, ny));
				}
				else {
					check.push_back(make_pair(nx, ny));
					findFish = 1;
				}
			}
		}
		if (findFish) {
			break;
		}
	}

	if (findFish) {
		int x = check[0].first, y = check[0].second;
		for (int i = 1; i < check.size(); i++) {
			if (check[i].second < y) {
				y = check[i].second;
				x = check[i].first;
			}
			else if (check[i].second == y) {
				if (x > check[i].first) {
					y = check[i].second;
					x = check[i].first;
				}
			}
		}
		map[y][x] = 0;
		g_shark.x = x;
		g_shark.y = y;
		answer += depth;
		return 1;
	}
	else {
		return 0;
	}
}

void solution()
{
	while (1) {
		if (moveShark()) {
			g_shark.size++;
			if (g_shark.size == g_shark.level) {
				g_shark.level++;
				g_shark.size = 0;
			}
		}
		else {
			return;
		}
	}
}

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
			if (map[i][j] == 9) {
				g_shark = { j, i, 0, 2 };
				map[i][j] = 0;
			}
		}
	}

	solution();
	printf("%d\n", answer);
}

 

결과