[백준/C++] 16236.아기상어

문제

www.acmicpc.net/problem/16236

16236번: 아기 상어

 

풀이

조건이 매우! 많은 문제였다. 

BFS를 통해서 풀어야 한다는건 알았지만, 계속 오답이 나와서 다른 분들의 풀이를 참고했다. 

 

yulme.tistory.com/92

rile1036.tistory.com/90

 

1. 우선순위 큐 사용 

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

--> 위의 조건을 적용시키기 위해서 우선순위 큐를 이용했다. 

큐에 여러개를 넣으면, 알아서 정렬해서 제일 먼저 먹어야할 물고기를 top에 위치시키도록 함. 

 

2. Fish 구조체 사용

Fish 구조체를 만들어 필요한 정보를 담고, 

우선순위 큐를 이용하기 위해 compare 함수를 정의해주었다.  

 

코드

#include<iostream>
#include <vector>
#include <queue>

using namespace std;
int N;
int table[20][20];
bool visited[20][20] = { 0, };
int baby_size = 2;
int move_count = 0;
int eat_count = 0;

int dc[4] = { -1,0,1,0 };
int dr[4] = { 0,-1,0,1 };

struct Fish {
	int dist;
	int r;
	int c;

	//우선순위 큐를 이용하기 위해 바꿔줌  
	bool operator < (const Fish &f) const {
		if (dist == f.dist) {
			if (r == f.r) {
				return c > f.c; // c기준 오름차순 
			}
			else return r > f.r; //r 기준 오름차순
		}
		else return dist > f.dist; // 거리 기준 오름차순 
	}
};
priority_queue<Fish> q;

void BFS() {
	while (!q.empty()) {
		int dist = q.top().dist;
		int c = q.top().c;
		int r = q.top().r;
		q.pop();

		if (table[r][c] > 0 && table[r][c] < baby_size) {
			eat_count++;
			table[r][c] = 0;
			if (baby_size == eat_count) {
				baby_size++;
				eat_count = 0;
			}
			move_count += dist; //상어가 이 물고기를 먹기까지 얼마나 움직였는지 더해줌

			dist = 0; //지금 위치부터 다시 다음 물고기까지 거리 재야하니 0으로 초기화
			fill(&visited[0][0], &visited[19][20],0); //방문 체크 초기화 

			while (!q.empty()) q.pop(); //큐 비워줌 (지금 자리부터 새로 채워야함)
		}

		for (int i = 0;i < 4;i++) {
			int new_r = r + dr[i];
			int new_c = c + dc[i];

			//범위 벗어나면 큐에 안 넣음
			if (new_r < 0 || new_r >= N || new_c < 0 || new_c >= N) continue;
			//이미 방문한 곳이면 안 넣음
			if (visited[new_r][new_c]) continue;
			// 아기 상어 크기보다 큰 물고기가 있으면 안 넣음
			if (table[new_r][new_c] > baby_size) continue;

			q.push({ dist + 1,new_r,new_c });
			visited[new_r][new_c] = 1;

		}
	}
}
int main(void) {
	int now_r, now_c;
	cin >> N;
	for (int i = 0;i < N;i++) {
		for (int j = 0;j < N;j++) {
			cin >> table[i][j];
			if (table[i][j] == 9) {
				table[i][j] = 0; //빈칸으로 만들어주기
				q.push({ 0,i,j });
			}
		}
	}
	BFS();
	cout << move_count << endl;
	return 0;
}

결과