[백준 16236] 아기상어

Algorithm/BOJ

[백준 16236] 아기상어

EVO. 2023. 5. 7. 21:08

처음 아기상어 크기: 2

1초에 상하좌우로 인접한 한 칸씩 이동

아기상어의 크기 < 물고기의 크기 : 그 칸으로 이동 불가능
아기상어의 크기 > 물고기의 크기 : 이동가능O 먹을 수 O
아기상어의 크기 = 물고기의 크기: 이동가능 O 먹을수 X

물고기 먹는 순서

1. 먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.(9는 상어)

0 0 0

1 0 9

2. 먹을 수 있는 물고기가 1마리보다 많다면 거리가 가장 가까운 물고기를 먹으러간다.

0 1 0

0 0 0

1 0 9

3. 거리가 같은 물고기가 많다면 가장위, 가장 왼쪽 물고기를 먹는다.

1 0 1

0 9 0

0 0 1

먹을 수 있는 물고기가 있는 칸으로 이동했다면 그 칸은 0이 된다.

아기상어는 자신의 크기와 같은 수의 물고기를 먹을 때마다 크기가 1증가한다.

크기가 2인 상어는 물고기를 두마리 먹고 크기가 3이 된다.

9 1 1

먹을 수 있는 물고기가 공간에 없다면 종료하고 이동하는데 걸린시간이 답이 된다

예를들어

이러한 입력이 주어지면 먼저 상어의 크기는 2이므로 크기가 1인 물고기만 먹을 수 있다. 그러한 물고기가 두 곳에 있는데 최단경로로 가는데 이 두곳의 길이가 같으므로 물고기 먹는 순서에 따르면 가장 위인 물고기부터 먹어야 한다. 따라서

파란색 1의 최단경로로 가는데 물고기의 크기의 규칙에 고려하여 가면 3이다.

4 3 2 1

0 0 0 0

0 0 9 0

1 2 3 4

이제 상어는 한마리만 더 먹으면 크기가 1증가하고 (아직 상어의 크기는 2) 크기가 1인 물고기가 1마리만 있으므로 거기까지 최단경로로 가는데 물고기의 크기의 규칙에 고려하며 가면 6이다(축적해야함. res = 3+6 = 9)

4 3 2 9

0 0 0 0

1 2 3 4

이제 상어의 크기는 3이다.(두개의 물고기를 먹었으므로) 크기가 3인 상어는 크기가 2이하의 물고기를 먹을 수 있다. 2인 물고기가 총 2마리 있는데 그중에 물고기먹는순서에 따르면 가장 가까운 파란색 2인 물고기를 최단경로로 물고기의 크기의 규칙에 고려하며 가면 1이다(res=9+1=10)

4 3 2 0

0 0 0 0

9 2 3 4

상어의 크기는 2마리를 더 먹으면 4가되고 아직 크기가 3인 상어는 2이하의 물고기가 하나이므로 거기를 향해 최단경로로 물고기의 크기의 규칙에 고려하며 가면 4이다(res=10+4=14)

4 3 2 0

0 0 0 0

0 9 3 4

이제 상어는 물고기 한마리를 더먹으면 4가되고 아직 크기가 3인 상어이다. 여기서 공간에 더이상 먹을 물고기가 없으므로 종료된다. 결과적으로 14이다.

4 3 9 0

0 0 0 0

0 0 3 4

1.일단 상어크기보다 작은 크기의 물고기수의 위치를 벡터에 저장한다. 만약 벡터에 들어있는게 없다면 종료

2.이좌표들의 최단경로를 구하고 제일 길이가 작은 것의 좌표들을 가져온다.

3.그 좌표들중 가장위가장왼쪽의 좌표를 가져온다. 그러고 좌표들을 저장한 벡터에 그 좌표를 뺀다

4.그 좌표의 위치로 간다. 그리고 먹은물고기수 증가 그리고 상어크기증가했는지 확인 크기가 증가했으면 1번으로 다시 간다.

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

int 상어크기 = 2;
int 먹은물고기수 = 0;

int stayTime = 0;
int N;
int arr[20][20];
//방문표시+거리표시
int visited[20][20];
int sx, sy; //아기 상어의 위치,현재위치


//위쪽 부터 탐색 그리고 왼쪽 탐색
int dx[4] = { -1,0,0,1 };//위,왼,오,아
int dy[4] = { 0,-1,1,0 };//위,왼,오,아



//위치 유효성 체크
bool isValid(int x, int y) {
	return (x >= 0 && x < N) && (y >= 0 && y < N);
}
struct node {
	int x, y;
};

int bfs(int endX, int endY)//목적지
{
	//현위치 
	queue<pair<int,int>> q;
	
	q.push({ sx,sy});

	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		int dis = visited[x][y];
		for (int i = 0; i < 4; i++)
		{
			int nextX = x + dx[i];
			int nextY = y + dy[i];
			//유효성 검사
			if (!isValid(nextX, nextY))continue;
			//목적지에 발견되면 바로 저장후 리턴
			if (nextX == endX && nextY == endY)return visited[nextX][nextY]  = dis+ 1;
			//목적지가 아니면 지나갈수있는 곳인지 확인
			//출발지점이면 넘기고
			if (nextX == sx && nextY == sy)continue;
			//상어가 물고기보다 작으면 넘김
			if (visited[nextX][nextY] != 0 || 상어크기 < arr[nextX][nextY])continue;
			else {
				visited[nextX][nextY] = dis + 1;
				q.push({ nextX,nextY });
			}
		}
	}
	return -1;

}
node whichFish(int storeX, int storeY, int i, int j) {
	//가장위
	if (storeX < i) {
		node res = { storeX,storeY };
		return res;
	}
	else if (i < storeX) {
		node res = { i,j };
		return res;
	}
	//가장 왼쪽
	if (storeY < j) {
		node res = { storeX,storeY };
		return res;
	}
	else if (j < storeY)
	{
		node res = { i,j };
		return res;
	}
}
void init() {
	int min = 1000;
	int storeX=sx;
	int storeY=sy;
	node res;
	//최단경로 길이 구하기
	
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (0 < arr[i][j] && arr[i][j] < 상어크기) {
				int len;
				memset(visited, 0, sizeof(visited));
				len = bfs(i, j); 
				//cout << "len의 길이: " << len << '\n';
				if (len != -1) {
					if (len < min) {
						min = len; 
						storeX = i;
						storeY = j;
					}//최단경로의 길이가 같으면
					else if (len == min)
					{
						//누굴 선택해야하는지 검사
						res = whichFish(storeX, storeY, i, j);
						storeX = res.x;
						storeY = res.y;
					}
				}
				
			}
		}
	}

	//현재위치 0으로 바꾸고
	arr[sx][sy] = 0;
	
	//전체를 살펴봤는데 갈곳이 없어서 len이 -1이라면 여기서 종료
	if (min == 1000) return;
	
	//시작위치 이동
	sx = storeX;
	sy = storeY;
	//그 위치도 0으로 초기화
	arr[sx][sy] = 0;
	stayTime += min;
}

int main() {

	cin >> N;
	//초기화
	memset(arr, -1, sizeof(arr));
	

	//입력 받기
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 9) {
				sx = i;
				sy = j;
			}

		}
	}

	while (true)
	{
		//cout << "res의 크기 " << stayTime << '\n';
		int prevX = sx;
		int prevY = sy;
		init();
		//cout << "도착 좌표 " << sx<<","<<sy << '\n';
		//여전히 이전값과 같다면 while문 탈출
		if (sx == prevX && sy == prevY)break;
		//그게 아니면 먹은물고기수 증가 그리고 상어크기증가했는지 확인
		먹은물고기수 += 1;
		if (먹은물고기수 == 상어크기) {
			상어크기 += 1; 
			먹은물고기수 = 0;
		}
	}


	cout << stayTime;



}

저작자표시

'Algorithm > BOJ' 카테고리의 다른 글

[백준 9466] 텀프로젝트 (0)	2023.06.03
[백준 15486] 퇴사2 (0)	2023.05.23
[백준 1475] 방번호 (0)	2023.05.03
[백준 14500] 테트로미노 (0)	2023.05.02
[백준 12100] 2048(Easy) (0)	2023.05.01

현재글[백준 16236] 아기상어

EVO