[백준/BOJ 알고리즘] 16236 아기상어 C++

> www.acmicpc.net/problem/16236

16236번: 아기 상어

아기 상어가 바다에서 엄마 상어 없이 얼마나 물고기를 잡아먹으며 버틸 수 있는가.. 하는 문제이다. 뚜루뚜두둡.

더 이상 먹을 물고기가 없을 때까지의 시간을 계산하여 출력하면 된다! 문제 조건이 생각보다 까다롭고 이해하기 어려워서 좀 헤맸던 문제이다...

처음엔 좌표와 비용을 갖는 이중pair(?) 자료형을 큐에 넣고 작업했는데, 시간초과가 나서 비용 정보를 갖는 배열을 생성해서 해결했다.

 

문제의 핵심 

• N의 최대값은 20이다. 무식하게 풀어도 가능하다.
• 물고기를 잡아먹었으면 그 자리를 0으로 만들어주어야한다.
• 몸집이 같으면 먹을 수 없다. 하지만 지나갈 수는 있다.
• 먹을 수 있는 물고기가 여럿이라면, 조건에 맞는 물고기를 먹어야한다. 
  • 거리가 가까운 물고기가 최우선순위이다.
  • 거리가 같은 물고기가 여럿이라면, 그 중 가장 위에서 왼쪽에 있는 물고기를 먹어야한다.
• 이동 비용을 계산하기 위한 별도의 공간이 필요하다.
• 먹을 수 있는 물고기를 발견했다고 바로 먹는 것이 아니다.
• 먹을 수 있는 물고기 중 최적의 조건에 있는 물고기를 먹어야하는 문제이다.

구현  

• 상어의 위치부터 시작해서 BFS 탐색을 시작한다.
• cost = costMap[현재좌표] +1 의 방식으로 현재 좌표까지 오는 데 드는 비용을 계산한다.
• 상어의 상하좌우를 탐색하며 조건에 따라 처리한다.
  • 이동하려는 곳에 본인보다 작은 물고기가 있다면,
    • 1. 현재의 비용(min_cost)을 변수에 저장한다. 이 비용은 물고기를 먹을 수 있는 최저비용 값이다.
    • 2. 큐에 현재 좌표 푸쉬 후 방문처리한다.
    • 3. costMap[현재좌표]에 비용을 저장한다. 
  • 이동하려는 곳에 본인과 크기가 같은 물고기가 있거나, 빈 칸일 경우,
    • 1. 큐에 현재 좌표 푸쉬 후 방문처리한다.
    • 2. costMap[현재좌표]에 비용을 저장한다.
• cost가 min_cost보다 커질 경우 물고기를 먹는다.
  • '가장 위에 있는 물고기, 그러한 물고기가 여럿이라면, 가장 왼쪽에 있는 물고기를 먹는다' 의 조건을 만족하기 위해서 costMap 배열을 for문을 통해 위의 왼쪽에서부터 탐색하여 min_cost 값을 갖는 물고기를 찾는다.
  • cost를 전체 비용에 추가하고, 현재 크기에서 먹은 물고기의 값을 증가시켜준다. 레벨업할만큼 먹었다면 크기를 올려준다.
  • 비용, 방문처리 배열과 큐를 초기화하고, 먹은 물고기의 위치에서부터 다시 탐색을 시작한다.

 

 

 

 

> 코드가 궁금하다면, 포스트 하단의 더보기를 눌러주세요

 

 

* 코드에 대한 피드백은 언제나 환영합니다. *

#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define lli long long int
#define MAX 21
using namespace std;
typedef pair<int ,int> p;

int map[MAX][MAX] = {};
int visited[MAX][MAX] = {};
int costMap[MAX][MAX] = {};
int dir[4][2] = {{-1,0}, {0,-1}, {0,1}, {1,0}};
queue<p> q;

void clearQ() {
	while(!q.empty()) q.pop();
}

p eat(int n, int size, int min) {
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			if(map[i][j] < size && map[i][j] && costMap[i][j] == min) {
				map[i][j] = 0;
				return mp(i,j);
			}
		}
	}
}

void solve(int n, p shark) {
	int cost = 0, ans = 0, evol = 2, size = 2, min_cost = 999;
	int dx, dy;
	p cur, best;
	q.push(shark);
	visited[shark.st][shark.nd] = 1;
	while(!q.empty()) {
		cur = q.front();
		q.pop();
		cost = costMap[cur.st][cur.nd] + 1;
		if(cost > min_cost) {
			best = eat(n, size, min_cost);
			ans += min_cost;
			if(!(--evol)) evol = ++size;
			cost = 0;
			memset(visited, 0, sizeof(visited));
			memset(costMap, 0, sizeof(costMap));
			clearQ();
			q.push(best);
			visited[best.st][best.nd] = 1;
			min_cost = 999;
			continue;
		}
		for(int i=0;i<4;i++) {
			dx = cur.st + dir[i][0];
			dy = cur.nd + dir[i][1];

			if(visited[dx][dy] || dx < 1 || dy < 1 || dx > n || dy > n) continue;
			if(map[dx][dy] && map[dx][dy] < size) { 
				min_cost = cost;
				q.push(mp(dx,dy));
				visited[dx][dy] = 1;
				costMap[dx][dy] = cost;
			}
			else if(!map[dx][dy] || map[dx][dy] == size) {
				q.push(mp(dx,dy));
				visited[dx][dy] = 1;
				costMap[dx][dy] = cost;
			}
		}
	}
	cout << ans;
} 

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
	int n;
	cin >> n;
	p shark;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			cin >> map[i][j];
			if(map[i][j] == 9) {
				shark = mp(i,j);
				map[i][j] = 0;
			}
		}
	} 
	solve(n, shark);
}