[백준 16236] 아기 상어

C 프로그래밍/BOJ 2022. 10. 4. 20:18

728x90

++ 22.10.24 다시 풀어봄 (52m)

아기 상어 처음 위치에서 자기보다 사이즈가 작은 물고기를 먹으러갈 때 까지 cost는 똑같기 때문에 사실 우선순위 큐를 쓸 필요는 없다.

FIFO 큐로도 구현 가넝..

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

16236번: 아기 상어

N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가

www.acmicpc.net

#include <cstdio>
#include <queue>
int N;
int board[20 + 2][20 + 2];
int visited[20 + 2][20 + 2];

struct _qt
{
	int x, y;
	int cnt;
};

struct _st
{
	int x, y;
	int size;
};

_st Shark[1];	// 아기상어
std::queue<_qt> Q;

void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &board[i][j]);
			if (board[i][j] == 9) {
				Shark[0].x = i;
				Shark[0].y = j;
				Shark[0].size = 2;
			}
		}
	}
}


int search()
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };

	std::fill(&visited[0][0], &visited[0][0] + sizeof(visited) / sizeof(int), 0);
	Q = {};
	Q.push({ Shark[0].x, Shark[0].y , 0});	// 아기 상어 현재 위치
	visited[Shark[0].x][Shark[0].y] = 1;

	int min = 0x7fffffff; int min_row = -1; int min_col = -1; bool set = false;

	while (!Q.empty()) {
		_qt data = Q.front();
		Q.pop();

		if (data.cnt > min) break;

		if (board[data.x][data.y] < Shark[0].size && board[data.x][data.y] != 0) {
			if ((min > data.cnt) ||
				(min == data.cnt && min_row > data.x) ||
				(min == data.cnt && min_row == data.x && min_col > data.y)) {
				min = data.cnt;
				min_row = data.x;
				min_col = data.y;
				set = true;
			}
		}

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
			if (visited[nx][ny]) continue;
			if (board[nx][ny] > Shark[0].size) continue;	// 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다. 
			Q.push({ nx, ny, data.cnt + 1 });
			visited[nx][ny] = visited[data.x][data.y] + 1;
		}
	}
	if (set == false) return -1;

	board[Shark[0].x][Shark[0].y] = 0;
	board[min_row][min_col] = 0;
	Shark[0].x = min_row;
	Shark[0].y = min_col;

	return min;
}




int simul()
{
	int time = 0;
	int eat = 0;

	while (1) {
		int cnt = search();
		if (cnt == -1) return time;
		time += cnt;
		
		eat++;
		if (eat == Shark[0].size) {
			eat = 0;
			Shark[0].size += 1;
		}
	}
}




int main()
{
	input();
	int ans = simul();
	printf("%d\n", ans);
	return 0;
}

++22.11.11 큐를 사용하여 다시 풀어봤지만 효율은 더 안좋은 코드..

코드트리에서 풀어봤다.

현재 로봇의 위치로부터 모든 몬스터들까지의 거리를 구하고, 그중 자신보다 레벨이 낮고 도달 가능한 위치에 존재하는 몬스터를 잡는다.

https://www.codetree.ai/frequent-problems/fighting-robot/description

코드트리

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

#include <cstdio>
#include <queue>
#include <cstring>
int N;
int board[20 + 2][20 + 2];
int sx, sy;
int level = 2;


struct _st
{
	int x, y;
};
std::queue<_st> Q;
int visited[20 + 2][20 + 2];



void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &board[i][j]);
			if (board[i][j] == 9) {
				sx = i;
				sy = j;
				board[i][j] = 0;	// 처음 로봇위치 초기화 필요	// 큰 몬스터로 인식한다.. 
			}
		}
	}
}


void BFS()
{
	// init 
	Q = {};
	memset(visited, -1, sizeof(visited));

	// dir
	int dir_x[4] = { 0, 0, 1, -1 };
	int dir_y[4] = { 1, -1, 0, 0 };

	Q.push({ sx, sy });
	visited[sx][sy] = 0;

	while (!Q.empty()) {
		_st data = Q.front();
		Q.pop();

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
			if (visited[nx][ny] >= 0) continue;
			if (board[nx][ny] > level) continue;	// 자신의 레벨보다 큰 몬스터가 있는 칸은 지나칠 수 없다. 
			Q.push({ nx ,ny });
			visited[nx][ny] = visited[data.x][data.y] + 1;
		}
	}
}



int get_min()
{
	// 현재 로봇 위치에서 각 몬스터들 까지의 거리 구하기 
	BFS();

	int min_dist = 0x7fffffff;
	int min_row = 0x7fffffff;
	int min_col = 0x7fffffff;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (board[i][j] == 0) continue;
			if (board[i][j] >= level) continue;
			if (visited[i][j] == -1) continue;
			int dist = visited[i][j];
			if ((dist < min_dist) ||
				(dist == min_dist && min_row > i) ||
				(dist == min_dist && min_row == i && min_col > j)) {
				min_dist = dist;
				min_row = i;
				min_col = j;
			}
		}
	}
	if (min_dist == 0x7fffffff) return -1;	// 없앨 수 있는 몬스터가 없다면 일을 끝낸다. 

	board[min_row][min_col] = 0;
	sx = min_row, sy = min_col;
	//printf("%d, %d]\n", level, min_dist);
	//debug();
	return min_dist;
}



int simul()
{
	int cnt = 0;
	int time = 0;

	while (1) {
		int spend = get_min();
		if (spend == -1) return time;
		time += spend;	// 몬스터가 1칸 이동하는데 1초가 걸린다. 
		cnt++;
		if (cnt == level) {
			level++;
			cnt = 0;
		}
	}
}



int main()
{
	input();
	int ans = simul();
	printf("%d\n", ans);
	return 0;
}

우선순위 큐를 사용한 이전의 코드..

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
int N;
int ocean[20 + 2][20 + 2];
int chk[20 + 2][20 + 2];	// 걸린 시간 담아주기 위해 
int sx, sy;		// 상어 위치 
int sz = 2;		// 상어 사이즈 

struct _qt
{
	int x;
	int y;
	int size;
	int cnt;
};

struct COMP
{
	bool operator()(_qt &a, _qt &b) {
		if (a.cnt == b.cnt && a.x == b.x) return a.y > b.y;		// 그러한 물고기가 여러마리라면 가장 왼쪽에 있는 물고기 
		if (a.cnt == b.cnt) return a.x > b.x;	// 거리가 가까운 물고기가 많다면 가장 위에 있는 물고기 
		return a.cnt > b.cnt;	// 거리가 가장 가까운 물고기를 먹으러 간다. 
	}
};


priority_queue<_qt, vector<_qt>, COMP> PQ;


void input()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &ocean[i][j]);
			if (ocean[i][j] == 9) {
				sx = i;
				sy = j;
			}
		}
	}
}



int BFS()
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };

	// BFS 여러번 돌리므로 초기화 
	fill(&chk[0][0], &chk[0][0] + sizeof(chk) / sizeof(int), -1);	// 아기상어 자기자신 0초부터 시작하므로
	PQ = {};

	PQ.push({ sx, sy, sz, 0 });	// 상어 처음위치, 사이즈, 걸린 시간 담아줌 
	chk[sx][sy] = 0;			// 상어 처음 위치에서 걸린 시간 표시 
	ocean[sx][sy] = 0;			// 시작위치 0으로 변경 

	while (!PQ.empty()) {
		_qt data = PQ.top();
		PQ.pop();

		if (ocean[data.x][data.y] != 0 && ocean[data.x][data.y] < data.size) {	// 해당 맵에 물고기가 있고, 현재 상어 사이즈보다 작으면 
			sx = data.x; sy = data.y;
			return chk[sx][sy];			//PQ를 사용했기 때문에 바로 리턴해줄 수 있음 
		}

		for (int p = 0; p < 4; p++) {
			int nx = data.x + dir_x[p];
			int ny = data.y + dir_y[p];
			int ncnt = data.cnt + 1;

			if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
			if (ocean[nx][ny] > sz) continue;				// 해당 위치의 물고기가 자신보다 큰 경우 스루 
			if (chk[nx][ny] != -1) continue;				// 이미 방문한 위치이면 스루 
			
			chk[nx][ny] = chk[data.x][data.y] + 1;			// 해당 위치까지 오는데 걸린 시간 저장
			PQ.push({ nx, ny, data.size, chk[nx][ny] });
		}
	}
	return chk[sx][sy];	// PQ에 아무것도 안들어가면 중간에 리턴 안되므로 처음 좌표의 체크 배열 위치 리턴해주어야 한다. 
}





int lets_eat()
{
	int total = 0;
	int ate = 0;
	while (1) {
		int tmp = BFS();	// 지금까지 몇초 걸렸는지  
		if (tmp == 0) break;
		total += tmp;
		ate++;
		if (ate == sz) {
			sz++;	// 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가한다. 
			ate = 0;
		}
	}
	return total;
}



int main()
{
	input();
	int ans = lets_eat();
	printf("%d\n", ans);
	return 0;
}

제 2의 인구이동이랄까.... 점심 즈음 내 멘탈을 박살냈던 문제 ㅋㅅㅋ

처음에 맨하튼 거리로 접근하다가 멸망했다. 최단 거리가 그 최단 거리가 아닌것을...

=> 이게 왜 안되냐하면 중간에 상어보다 사이즈가 큰 물고기를 지나서 갈 수 없기 때문이다. 나는 처음에 맨하튼 거리로 상어보다 사이즈가 작은 물고기들을 모두 벡터에 저장하고, 그 벡터를 문제가 준 "가까운 물고기를 정하는 기준"으로 정렬하고 상어를 움직였다. 근데 이렇게 하면 상어 자신보다 사이즈가 같거나 작은 물고기들만 지나갈 수 있다는 문제의 조건에 위배된다. ~~(이걸 캐치 못하고 1시간 반을 좋다고 코드 짰다 ㅋ.. 이렇게 짜면 예제 6이 41로 나올 것임 ㅋ)~~

큐에서 원소를 뽑아 이동하면서 상어에서 각 물고기마다의 위치를 갱신해주고, 현재 상어보다 사이즈가 작으면서 가장 가까운 거리(이 기준은 우선순위 큐에 정의함)에 있는 물고기를 먹기 위해 걸린 시간을 구해야 했던 문제이다.

이를 위해 우선순위 큐 PQ는 다음과 같이 정의했다.

struct COMP
{
	bool operator()(_qt &a, _qt &b) {
		if (a.cnt == b.cnt && a.x == b.x) return a.y > b.y;		// 그러한 물고기가 여러마리라면 가장 왼쪽에 있는 물고기 
		if (a.cnt == b.cnt) return a.x > b.x;	// 거리가 가까운 물고기가 많다면 가장 위에 있는 물고기 
		return a.cnt > b.cnt;	// 거리가 가장 가까운 물고기를 먹으러 간다. 
	}
};


priority_queue<_qt, vector<_qt>, COMP> PQ;

// lets_eat( ) 함수

아기상어가 엄마상어에게 도움을 요청하지 않고, 몇 초 동안이나 맵을 돌면서 물고기를 잡아먹을 수 있는지 구해야 하므로 while 문을 돌리면서 BFS( ) 를 호출했다. 만약 BFS 함수의 리턴값이 0이면, 물고기를 한 마리도 잡아먹지 못한 것이므로 루프를 탈출한다. 만약 리턴값이 0보다 크다면 total(전체 걸린시간)에 누적하고, 물고기를 한 마리 먹었다는 의미에서 ate 변수를 증가시킨다.

이때 ate변수가 상어의 사이즈 sz와 같아지면 sz를 1만큼 증가시킨다.

// BFS( ) 함수

우선순위 큐를 이용했을 때 BFS 함수를 굉장히 깔끔하게 구현할 수 있다.

해당 함수가 여러번 초기화 되므로, 상어에서 각 물고기까지 걸린 시간 chk 배열과 PQ를 초기화해주어야 한다.

그리고 가장 처음 아기상어의 위치 (sx, sy)와 사이즈 sz를 큐에 삽입한다.

아기상어가 처음 위치한 곳까지 걸린 시간은 당연히 0일 것이고, ocean 배열의 해당 위치를 0으로 만들어 준다. 이는 "물고기를 먹으면 그 칸은 빈칸이 된다"는 조건을 만족하기 위함이다.

이제 우선순위 큐가 비어질 때 까지 루프를 도는데,

인접한 곳을 탐색하면서 만약 해당 위치의 물고기가 자신보다 큰 경우 스루한다.

또한 이미 방문한 위치이면 스루한다.

만약 위의 두 조건을 모두 만족하지 않는다면 chk배열의 (nx, ny)칸을 현재위치까지 오는데 걸린 시간 + 1로 갱신한다. 그리고 해당 위치까지 오는데 걸린 시간을 좌표 및 상어 사이즈와 함께 PQ에 삽입한다.

탐색 과정에서 만약 [*]PQ에서 pop한 (data.x, data.y) 좌표에 물고기가 존재하고, 해당 물고기의 사이즈가 현재 아기상어 사이즈보다 작다면 그 물고기를 잡아먹는다.

이때 PQ를 사용하지 않았다면, 같은 거리에 있는 모든 물고기들을 다 탐색하고 더 위쪽 그리고 더 왼쪽에 있는 물고기인지 판단해야 하는데, 정렬 조건을 준 PQ를 사용했으므로 이 과정이 필요 없다.

따라서 [*]의 조건을 만족한다면 아기상어의 시작위치 sx, sy를 data.x, data.y로 갱신하고 (해당 위치의 물고기를 잡아먹었으므로 BFS를 호출할 때 상어의 위치는 잡아먹은 물고기의 위치가 됨) chk[sx][sy]를 리턴한다.

728x90

'C 프로그래밍 > BOJ' 카테고리의 다른 글

[백준 19238] 스타트 택시 (0)	2022.10.06
[백준 17822] 원판 돌리기 (0)	2022.10.05
[백준 16235] 나무 재테크 (0)	2022.10.03
[백준 14891] 톱니바퀴 (0)	2022.10.03
[백준 11562] 백양로 브레이크 (0)	2022.10.02

ABOUT ME

달리기록 달리기록

'C 프로그래밍 > BOJ' 카테고리의 다른 글

티스토리툴바

ABOUT ME

'C 프로그래밍 > BOJ' 카테고리의 다른 글

관련글 관련글 더보기

티스토리툴바