[BOJ-16236] 아기상어

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

16236번: 아기 상어

 

2019년 하반기 모 기업의 코딩테스트 문제 입니다.

 

'거리가 가장 가까운 물고기를 먹는데 거리가 같을 경우 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면 가장 왼쪽에 있는 물고기를 먹는다' 이 부분을 구현하는 것에서 생각을 많이 했던 문제입니다.

 

이 부분을 제외하고는 bfs로 탐색하며 상어의 크기보다 작은 물고기를 찾아서 큐에 넣어주면서 반복하면 되고, 먹을 물고기를 찾았을 때 물고기를 먹고 상어의 크기만큼 물고기를 먹었을 때, 상어의 크기를 1 증가시켜주면 됩니다.

 

위에 언급했던 것 말고는 구현하는데 큰 어려움을 겪은 것은 없었고 개인적으로, 전에 포스팅했던 인구이동 문제보다는 조금 쉬운 문제였던것 같습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>

using namespace std;

struct SHARK {
	int y, x, time;
};
int n, res;
int shark_size = 2, eat_shark;
int map[20][20];
const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };
SHARK shark;

int main(void) {

	scanf("%d", &n);

	for (int y = 0; y < n; y++) {
		for (int x = 0; x < n; x++) {
			scanf("%d", &map[y][x]);

			if (map[y][x] == 9) {
				shark.y = y, shark.x = x, shark.time = 0;
				map[y][x] = 0;
			}
		}
	}

	bool flag = true;

	while (flag) {
		flag = false;

		bool visited[20][20] = { 0, };

		visited[shark.y][shark.x] = 1;
		queue<SHARK> q;
		q.push(shark);
		
		SHARK candi;

		candi.y = 22, candi.time = 0x7fffffff;

		while (!q.empty()) {
			SHARK cur = q.front(); q.pop();

			for (int dir = 0; dir < 4; dir++) {
				SHARK next;

				next.y = cur.y + dy[dir];
				next.x = cur.x + dx[dir];
				next.time = cur.time + 1;

				if (next.y < 0 || next.y >= n || next.x < 0 || next.x >= n) continue;
				if (visited[next.y][next.x] == 0 && map[next.y][next.x] <= shark_size) {

					if (map[next.y][next.x] < shark_size) {
						if (map[next.y][next.x] != 0 && next.time < candi.time) {
							flag = true;
							candi = next;
						}
						else if (map[next.y][next.x] != 0 && next.time == candi.time) {
							if (next.y < candi.y || (candi.y == next.y && candi.x > next.x)) {
								flag = true;
								candi = next;
							}
						}
					}

					visited[next.y][next.x] = 1;
					q.push(next);
				}
			}
		}

		if (flag) {
			eat_shark += 1;
			shark = candi;
			map[shark.y][shark.x] = 0;

			if (eat_shark == shark_size) {
				shark_size += 1;
				eat_shark = 0;
			}
		}
	}

	printf("%d\n", shark.time);

	getchar();
	getchar();

	return 0;
}