16236 아기 상어

www.acmicpc.net/problem/16236

16236번: 아기 상어

 

끔찍한 구현 문제였다. 어떻게 구현해야 할지 생각이 안 나서 다른 풀이를 참고했는데

pair 객체를 통해 정렬해주면 쉽게 풀리는데 잘 익혀둬야겠다.

 

• 더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게 도움을 요청한다.
• 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.
• 먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기를 먹으러 간다.
  • 거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야 하는 칸의 개수의 최솟값이다.
  • 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.

 

문제에서 요구하는 조건을 잘 충족시켜줘야 하는데

일단 큰 틀을 짜보면 shark 구조체를 만들어두고 상어가 이동할 때마다 shark 구조체로 접근하면 된다.

 

• 상어 구조체는 x, y, size(상어의 크기), eat(얼마나 먹었는지)로 설정해주고
• 입력받을 때 상어가 있는 위치에서 shark = { i,j,2,0 }으로 입력받는다
• 상어의 위치에서 BFS를 돌리는데 BFS를 통해 조건에 맞는 먹이가 있다면 feed 벡터에 push 해준다
• 먹이가 없을 때까지 이동하는데 먹이가 없는 조건은
  • 아기 상어보다 더 작은 물고기가 없는 경우
  • map에 먹이가 없는 경우
• 이외에 먹이가 있다면 feed 벡터를 정렬하고
• 위치 값과 ans를 갱신해준다

 

이런 틀로 접근했다.

 

input 파트부터 보면

 

	cin >> n;
	for (int i=0;i<n;++i)
		for (int j = 0; j < n; ++j) {
			cin >> ar[i][j];
			if (ar[i][j] == 9) { //상어가 있는 자리라면
				ar[i][j] = 0; //0으로 만들어주고
				shark = { i,j,2,0 }; //상어의 위치를 넣어준다
			}   //상어는 i, j 에 있고 시작 크기는 2이다
		}

 

 

process 과정을 보면

 

	while (1) {
		bfs(shark.x, shark.y); //상어의 시작 위치에서 BFS

		if (feed.empty()) break; //조건에 맞는 먹이가 없다면 종료
		else {
			sort(feed.begin(), feed.end()); //정렬하고 갱신

			shark.x = feed[0].second.first;
			shark.y = feed[0].second.second;
			ans += feed[0].first;
			++shark.eat;

			ar[shark.x][shark.y] = 0; //맵 갱신
            //아기 상어가 먹은 먹이가 size와 같다면 size + 1
			if (shark.sz == shark.eat) shark.eat = 0, ++shark.sz;
		}
	}

 

이제 제일 중요한 BFS 부분인데 BFS를 통해서 조건에 맞는 먹이를 잘 구해줘야 한다.

 

void bfs(int x, int y) {
	fill(&d[0][0], &d[20][21], 0); //거리값은 BFS 돌릴 때마다 0으로 초기화
	queue<pair<int, int>> q;
	feed.clear(); //feed도 BFS할 때마다 초기화
	
	q.push({ x,y });

	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		for (int i = 0; i < 4; ++i) {
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue; //범위 밖에 있다면 pass
            // 방문하지 않았고, 상어의 크기가 더 크다면
			if (d[nx][ny] == 0 && shark.sz >= ar[nx][ny]) {
				d[nx][ny] = d[cur.first][cur.second] + 1; //거리값 갱신하고 큐에 넣어준다
                q.push({ nx,ny });
                //맵에 먹이가 존재하고, 상어보다 작다면 
				if (ar[nx][ny] && shark.sz > ar[nx][ny])
                	//조건에 맞는 먹이니까 feed에 넣어준다
					feed.push_back({ d[nx][ny],{nx,ny} });
			}
		}
	}
}

 

중요한 점은 feed 벡터를 선언할 때, pair의 우선순위가 dist, x, y 순으로 와야 sort 할 때 우선순위가 

거리가 가장 작은 순, 가장 위쪽, 왼쪽 순을 맞출 수 있다.

아니라면 따로 람다 함수를 작성하던가 bool comp를 작성해서 맞춰줘야 한다.

 

전체 소스 코드

 

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct Shark { int x, y, sz, eat; };
int n, ans, ar[21][21], d[21][21];
vector<pair<int, pair<int, int>>> feed;
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
Shark shark;

void bfs(int x, int y) {
	fill(&d[0][0], &d[20][21], 0);
	queue<pair<int, int>> q;
	feed.clear();
	
	q.push({ x,y });

	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		for (int i = 0; i < 4; ++i) {
			int nx = cur.first + dx[i];
			int ny = cur.second + dy[i];
			if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			if (d[nx][ny] == 0 && shark.sz >= ar[nx][ny]) {
				d[nx][ny] = d[cur.first][cur.second] + 1;
				q.push({ nx,ny });

				if (ar[nx][ny] && shark.sz > ar[nx][ny])
					feed.push_back({ d[nx][ny],{nx,ny} });
			}
		}
	}
}

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

	cin >> n;
	for (int i=0;i<n;++i)
		for (int j = 0; j < n; ++j) {
			cin >> ar[i][j];
			if (ar[i][j] == 9) {
				ar[i][j] = 0;
				shark = { i,j,2,0 };
			}
		}

	while (1) {
		bfs(shark.x, shark.y);

		if (feed.empty()) break;
		else {
			sort(feed.begin(), feed.end());

			shark.x = feed[0].second.first;
			shark.y = feed[0].second.second;
			ans += feed[0].first;
			++shark.eat;

			ar[shark.x][shark.y] = 0;
			if (shark.sz == shark.eat) shark.eat = 0, ++shark.sz;
		}
	}

	cout << ans << endl;

	return 0;
}