백준 16236 아기상어 c++

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

16236번: 아기 상어

 

 

엄청난 시도 후 전장에서 승리하고 글을 작성합니다.

 

아기상어의 크기보다 작은 것만 섭취가능

아기상어의 위치는 9로 나타냄

아기상어의 크기만큼 섭취를 한다면, 크기가 1 커진다. 

bfs로 작은게 있는지 판단 -> 판단 후 있다면 상하좌우 위치 가중치 

	while (true) {
		if (hunt(k)) {
			continue;
		}
		else {
			break;
		}
	}

메인 알고리즘은 hunt에서 false 즉, 다 돌아봤는데 상어크기보다 작은 게 없으면 false를 return 해서 프로그램이 종료합니다.

 

 

struct shark {
	int y;
	int x;
	
	int size;
	int eat;
};

구조체로 shark에 대한 정보 위치, 크기, 몇 마리를 먹었는지 채크하는 구조체

while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
		//위치가 아기상어 본위치가 아니고, 0이 아니고, 아기상어 size보다 작아야 함 
		//이 조건을 충족시키면 들어가서 상하좌우 비교하고 

		q.pop();
		if (sea[y][x] != 9 && sea[y][x] != 0 && sea[y][x] < s.size) { continue; }
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= 0 && ny < n && nx >= 0 && nx < n && dist[ny][nx] == -1 && sea[ny][nx] <= s.size) {
				dist[ny][nx] = dist[y][x] + 1;
				q.push({ ny,nx });
			}
		}
	}

 

상하좌우를 비교하는데 그 위치에 방문을 했는지, 상어크기보다 작은지를 비교하고 작다면 현제위치 +1을 넣어준다. 

	int my = 100;
	int mx = 100;
	int m_dist = 401;
	for (int i = n - 1; i >= 0; i--) {
		for (int j = n - 1; j >= 0; j--) {
			if (sea[i][j] != 0 && sea[i][j] != 9 && sea[i][j] < s.size && dist[i][j] != -1 && dist[i][j] <= m_dist) {
				m_dist = dist[i][j];
				my = i;
				mx = j;
			}
		}
	}
	if (m_dist == 401) {
		return false;
	}
	else {
		sea[s.y][s.x] = 0;
		s.y = my;
		s.x = mx;
		s.eat++;
		if (s.eat == s.size) {
			s.eat = 0;
			s.size++;
		}
		sea[my][mx] = 9;
		ans += dist[my][mx];
		return true;
	}
}

상어로부터 거리가 가장가깝고, 왼쪽 위에 있는 우선순위를 가지는 먹이를 찾는 코드이다. 

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#pragma warning(disable : 4996);
using namespace std;
#include <queue>

int sea[21][21];
int ans = 0;
int n;

struct shark {
	int y;
	int x;
	
	int size;
	int eat;
};
int dist[21][21];
int dy[4] = { 1,-1,0,0 };
int dx[4] = { 0,0,1,-1 };
bool hunt(shark& s) {
	queue <pair<int, int>>q;
	//거리
	for (int i = 0; i < 21; i++) {
		for (int j = 0; j < 21; j++) {
			dist[i][j] = -1;
		}
	}
	// 거리 초기화
	q.push({ s.y,s.x }); // 아기상어 위치
	dist[s.y][s.x] = 0;  // 아기상어 위치 거리 가중치

	while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
		//위치가 아기상어 본위치가 아니고, 0이 아니고, 아기상어 size보다 작아야 함 
		//이 조건을 충족시키면 들어가서 상하좌우 비교하고 

		q.pop();
		if (sea[y][x] != 9 && sea[y][x] != 0 && sea[y][x] < s.size) { continue; }
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny >= 0 && ny < n && nx >= 0 && nx < n && dist[ny][nx] == -1 && sea[ny][nx] <= s.size) {
				dist[ny][nx] = dist[y][x] + 1;
				q.push({ ny,nx });
			}
		}
	}
	//비교 후 해당하는 값에대해서는 queue에 대입

	int my = 100;
	int mx = 100;
	int m_dist = 401;
	for (int i = 0; i <n ; i++) {
		for (int j = 0; j < n ; j++) {
			if (sea[i][j] != 0 && sea[i][j] != 9 && sea[i][j] < s.size && dist[i][j] != -1 && dist[i][j] < m_dist) {
				m_dist = dist[i][j];
				my = i;
				mx = j;
			}
		}
	}
	if (m_dist == 401) {
		return false;
	}
	else {
		sea[s.y][s.x] = 0;
		s.y = my;
		s.x = mx;
		s.eat++;
		if (s.eat == s.size) {
			s.eat = 0;
			s.size++;
		}
		sea[my][mx] = 9;
		ans += dist[my][mx];
		return true;
	}
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);


	cin >> n;
	int nx, ny;
	shark k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> sea[i][j];
			if (sea[i][j] == 9) {

				k.y = i;
				k.x = j;
				k.size = 2;
				k.eat = 0;
			}
		}
	}
	while (true) {
		if (hunt(k)) {
			continue;
		}
		else {
			break;
		}
	}
	cout << ans << endl;


	return 0;
}