BOJ - 아기상어(16236)

BFS를 응용해서 풀 수 있는 문제입니다. BFS를 통해서 먹을 수 있으면서 우선순위가 가장 높은 물고기를 찾습니다. 가장 가까운 물고기가 우선순위가 가장 높은 것이 아니기 때문에 주의해야 합니다. 우선순위가 가장 높은 물고기를 찾으면 잡은 시간을 저장하고 공간에서 물고기를 지워줍니다. 잡을 수 있는 물고기가 더 이상 없을 때 까지 반복을 합니다. 더 이상 잡을 수 있는 물고기가 없는 경우 마지막에 잡은 시간을 출력해주고 종료합니다.

풀이 코드

#include <stdio.h>

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

int N;

int map[20][20];
int queue[500][4]; //y, x, age, time;
int head;
int tail;

int ans;
int cur_y, cur_x, cur_age, cur_time;
int eat_count;

bool comp(int time1, int y1, int x1, int time2, int y2, int x2) {
	if (time1 < time2) return true;
	else if (time1 > time2) return false;
	else {
		if (y1 < y2) return true;
		else if (y1 > y2) return false;
		return x1 < x2;
	}
}

int bfs() {
	
	// 
	bool visited[20][20] = { 0, };

	// init
	head = 0;
	tail = 0;

	// enqueue
	queue[tail][0] = cur_y;
	queue[tail][1] = cur_x;
	queue[tail][2] = cur_age;
	queue[tail][3] = cur_time;
	tail++;

	// visited
	visited[cur_y][cur_x] = true;

	// selected
	cur_y = 999;
	cur_x = 999;
	cur_time = 999;

	while (head != tail) {
		
		// dequeue
		int y = queue[head][0];
		int x = queue[head][1];
		int age = queue[head][2];
		int time = queue[head][3];
		head++;

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

			if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if (visited[ny][nx] == true) continue;
			if (map[ny][nx] > age) continue;
			else {
				visited[ny][nx] = true;

				// 먹을 수 있으면 우선순위가 가장 높은 물고기를 보관
				if (map[ny][nx] != 0 && map[ny][nx] < age && comp(cur_time, cur_y, cur_x, nt, ny, nx) == false) {
					cur_time = nt;
					cur_y = ny;
					cur_x = nx;
					cur_age = age;
					
					// 마지막으로 잡았을 때 시간
					ans = nt;
				}

				// enqueue
				queue[tail][0] = ny;
				queue[tail][1] = nx;
				queue[tail][2] = age;
				queue[tail][3] = nt;
				tail++;
			}
		}
	}
	
	// 하나라도 잡는 경우
	if (cur_time != 999) {
		// 물고기 지우기
		map[cur_y][cur_x] = 0;

		// 먹은 수 늘림
		eat_count++;

		// 먹은수랑 나이랑 같은 경우 나이 증가
		if (eat_count == cur_age) {
			cur_age++;
			eat_count = 0;
		}
	}

	return cur_time;
}

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) {
				map[i][j] = 0;
				cur_y = i;
				cur_x = j;
			}
		}
	}


	cur_age = 2;
	while (true) {

		int dis = bfs();

		// 더이상 잡을게 없을 때 끝
		if (dis == 999) {
			printf("%d", ans);
			return 0;
		}

	}

	return 0;
}