BOJ : 16236 아기 상어

입력

첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다.

둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다.

• 0: 빈 칸
• 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기
• 9: 아기 상어의 위치

아기 상어는 공간에 한 마리 있다.

출력

첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다.

 

---

[BOJ 16236(G5) 리뷰]

골드5문제라 간단한 BFS일줄 알았는데 은근 조건이 까다로워서 푸는데 애를 먹었다.

BFS를통해 아기 상어가 먹을 수 있는 물고기의 거리를 재고, 가장 가까운 먹이를 먹어야 한다.

먹이를 먹을수록 아기 상어의 크기는 점점 커져 점점 큰 물고기를 먹을 수 있게 된다.

옛날에 비슷한 게임을 해본적이 있어 문제이해는 어렵지 않았으나 구현은 조금 까다로웠다.

 

먼저 아기상어의 좌표값을 기준으로 BFS를 수행한다. 아기상어의 크기보다 큰 물고기는 먹지 못하므로 거리를 잴 필요가 없고 아기 상어보다 작은 물고기의 거리를 계산한 후 가장 적게 걸리는 위치로 가서 물고기를 잡아먹으면 된다.

이렇게 구현이 끝난다면 좀 쉬웠겠지만 고려해야할 문제가 있다.

아기상어의 위치에서 먹을 수 있는 물고기의 위치가 여러개일 경우이다. 이때는 문제에서 제시해준대로 아기상어 기준 위쪽,왼쪽에 있는 물고기를 먼저 먹어야한다. 첨에 이걸 잘못 이해하고 구현해서 틀렸다.

 

이 문제를 해결하기위해서, 만약 먹을 수 있는 물고기가 있다면 먼저 후보벡터에 PUSH한다음 flag를 남긴다.

flag를 확인한 후 후보 다음 위치가 이미 후보물고기의 위치보다 큰 경우라면 더 이상 탐색할 필요가 없으므로 반복문을 종료하고 물고기를 잡아먹는 과정을 진행한다.

후보물고기를 sort한 후에 0번 인덱스에 있는 좌표로 가서 물고기를 먹으면 가장 위쪽,왼쪽에 있는 물고기 먼저 먹을 수 있다. 말로 설명하니 간단하지만 아이디어가 떠오르지 않아 다른 블로그를 참고했다.

 

구조체를 사용했다면 조금 더 편리했을텐데 아직 익숙하지가 않다.

---

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

#define X first
#define Y second

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


int map[21][21];
int dist[21][21];
pair <int, int> shark;
vector <pair<int, int>> candidate;
int sharksize = 2;
int food = 0;
int ans = 0;

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

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

	while (1)
	{
		for (int i = 0; i < N; i++)
			fill(dist[i], dist[i] + N, -1);

		queue <pair<int, int>> Q;
		candidate.clear();
		dist[shark.X][shark.Y] = 0;
		Q.push({ shark.X,shark.Y });
		int eat = false;
		while (!Q.empty())
		{
			auto cur = Q.front(); Q.pop();
			if (eat)
			{
				auto can = candidate[0];
				if (dist[cur.X][cur.Y] >= dist[can.X][can.Y])
					break;
			}
			
			for (int dir = 0; dir < 4; dir++)
			{
				int nx = cur.X + dx[dir];
				int ny = cur.Y + dy[dir];
				if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
				if (sharksize < map[nx][ny] || dist[nx][ny]!=-1) continue;
				if (map[nx][ny] != 0 && map[nx][ny] != 9 && map[nx][ny]<sharksize)
				{
					candidate.push_back({ nx,ny });
					eat = true;
				}
				dist[nx][ny] = dist[cur.X][cur.Y]+1;
				Q.push({ nx,ny });
			}
		}

		if (eat)
		{
			sort(candidate.begin(), candidate.end());
			auto nxt = candidate[0];
			food++;
			map[nxt.X][nxt.Y] = 9;
			map[shark.X][shark.Y] = 0;
			ans += dist[nxt.X][nxt.Y];
			shark = { nxt.X,nxt.Y };
		}
		else
			break;

		if (sharksize == food)
		{
			food = 0;
			sharksize++;
		}

	}
	cout << ans;


	
	
}