[Algorithm][C++] BOJ 16236 아기 상어

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

16236번: 아기 상어

 

풀이 핵심

1. BFS 활용

가장 가까운 물고기를 먹으러 간다

 

2. 우선 순위 큐 활용 (algorithm 헤더의 sort() 함수를 이용)

 

거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.

거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

 

거리가 가장 가까운 -  가장 위쪽 -  가장 왼쪽 순으로 큐를 정렬하기 위해 정렬의 기준이 되는 compare() 함수를 다음과 같이 구성하였다.

 

int compare(shark &a, shark &b) {
	if (a.dist == b.dist) {
		if (a.r == b.r) return a.c < b.c;
		else return a.r < b.r;
	}
	else return a.dist < b.dist;
}

 

정렬은 큐에 새로운 요소를 추가할 때마다 진행해준다.

 

void push(int r, int c, int dist) {
	q[re].r = r, q[re].c = c, q[re++].dist = dist;
	std::sort(q + fr, q + re, compare);
}

 

3. 현재 탐색 위치의 상어의 크기가 자신보다 작다면 상어를 먹은 뒤 현재의 거리를 정답에 더한다.

현재 거리, 큐, visited 배열을 초기화 해준다.

 

4. 상어를 먹고 난 뒤 먹은 횟수가 자신의 크기와 같다면 먹은 횟수를 초기화 하고 자신의 크기를 증가 시킨다.

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>

int N, body = 2, eat, ans;
int map[20][20];
bool visited[20][20];

struct shark { int r, c, dist; };
int compare(shark &a, shark &b);
shark q[20 * 20];
int fr, re;
void push(int r, int c, int dist);
shark front();
void pop();
bool isEmpty();

void InitializeVisit();
void BFS();

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) {
				push(i, j, 0);
				map[i][j] = 0;
				visited[i][j] = true;
			}
		}
	}
	BFS();
	printf("%d", ans);
	return 0;
}

int compare(shark &a, shark &b) {
	if (a.dist == b.dist) {
		if (a.r == b.r) return a.c < b.c;
		else return a.r < b.r;
	}
	else return a.dist < b.dist;
}
void push(int r, int c, int dist) {
	q[re].r = r, q[re].c = c, q[re++].dist = dist;
	std::sort(q + fr, q + re, compare);
}
shark front() { return q[fr]; }
void pop() { fr++; }
bool isEmpty() { return fr == re; }

void InitializeVisit() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visited[i][j] = false;
		}
	}
}

void BFS() {
	const int dr[] = { 1,-1,0,0 };
	const int dc[] = { 0,0,1,-1 };
	while (!isEmpty()) {
		shark cur = front();
		pop();
		if (map[cur.r][cur.c] && map[cur.r][cur.c] < body) {
			map[cur.r][cur.c] = 0;
			eat++;
			if (eat == body) {
				body++;
				eat = 0;
			}
			ans += cur.dist;
			cur.dist = 0;
			InitializeVisit();
			fr = re = 0;
		}
		for (int dir = 0; dir < 4; dir++) {
			int nr = cur.r + dr[dir];
			int nc = cur.c + dc[dir];
			if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
			if (visited[nr][nc] || map[nr][nc] > body) continue;
			push(nr, nc, cur.dist + 1);
			visited[nr][nc] = true;
		}
	}
}