백준 16236번: 아기 상어

문제

문제 바로가기> 백준 16236번: 아기 상어

풀이

bfs 탐색을 이용해 조건(가장 가까운, 거리가 같다면 가장 위, 그러한 물고기가 여러마리라면 가장 왼쪽)을 만족하는 물고기부터 잡아 먹으며 거리를 더해주었다. 이 때 조건에 따른 우선순위를 쉽게 구현 위해서 priority queue와 shark 구조체를 사용해주었다. shark 구조체에서는 연산자 오버로딩을 통해 조건에 따른 우선순위를 구현해주었다. (이때 멤버 함수를 struct 내부에 쓰기 위해서는 const로 해주어야 한다.)

연산자 오버로딩: 사용자 정의 타입(class나 struct)에 관한 연산자를 정의하여 좀더 편하게 사용할 수 있게 만든 C++의 문법적 기능

#include<iostream>
#include<cstring>
#include<queue>
#define MAX_N 21
using namespace std;

struct shark{
    int d, y, x; // 거리, y좌표, x좌표
    bool operator < (const shark &t) const{ // (연산자 오버로딩, 비교 순서) 거리 > 상 > 좌
        if(d == t.d){ // 거리가 같다면
            if(y == t.y) return x > t.x; // y(상하)좌표도 같다면, 왼쪽에 있는 것 우선! 
            else return y > t.y; // y좌표가 다르다면 위에 있는 것 우선!
        }
        else return d > t.d; // 거리가 다른 경우 짧은 거리 우선
    }
};

int N, shark_size=2, eat=0, ans=0;
int space[MAX_N][MAX_N];
bool check[MAX_N][MAX_N];
int dy[] = {-1, 1, 0, 0}, dx[] = {0, 0, -1, 1}; // 상 하 좌 우
priority_queue<shark> pq;

void bfs(){
    while (!pq.empty()){
        int d = pq.top().d;
        int y = pq.top().y;
        int x = pq.top().x;
        pq.pop();

        if(0 < space[y][x] && space[y][x]<shark_size){ // 물고기를 잡아 먹을 수 있는 경우
            space[y][x] = 0; // 잡아 먹고
            eat++; // 잡아 먹은 수를 증가
            if(eat == shark_size){ // 자신의 크기 만큼 잡아 먹었다면
                shark_size++; // 크기 증가
                eat = 0; // 크기 업데이트 후 먹은 물고기가 아직 없으므로, 다시 0으로 설정!
            }
            ans+=d; // 물고기를 먹기위해 이동한 거리를 더해줌
            d=0; // 거리 초기화! (다시 이 지점(y, x)부터 탐색 시작)
            memset(check, false, sizeof(check)); // 방문 여부 배열 초기화
            while (!pq.empty()) pq.pop(); // pq를 비워줌
        }

        for(int i=0; i<4; i++){
            int ny = y+dy[i], nx = x+dx[i];
            if(ny<1 || ny>N || nx<1 || nx>N) continue; // space를 벗어나는 경우
            if(check[ny][nx]) continue; // 이미 방문한 경우 
            if(0<space[ny][nx] && shark_size<space[ny][nx]) continue; // 상어보다 큰 물고기인 경우
            pq.push({d+1, ny, nx}); // 앞에 경우들이 아닌 경우 pq에 넣고,
            check[ny][nx] = true;  // 방문 여부를 true로 update
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++) {
            cin >> space[i][j];
            if(space[i][j] == 9){ 
                pq.push({0, i, j}); // 시작 좌표 저장
                space[i][j] = 0; 
            }
        }
    }
    bfs(); // bfs 탐색을 진행하며 답을 구함
    cout << ans;
}

비교 연산자를 전역으로 사용하는 경우

bool operator < (const shark &a, const shark &b) {
    if (a.d != b.d){
        if(a.y == b.y) return a.x > b.x;
        else return a.y > b.y; 
    }
    else return a.d > b.d;
}

풀이2

#include<iostream>
#include<vector>
#include<queue>
#define MAX 21
#define EMPTY 0
#define INF 987654321
using namespace std;

struct FISH {
	int y, x, s, cnt;
} shark;

int N;
int map[MAX][MAX];
int dist[MAX][MAX];
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };

void input() {
	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) { // 상어의 초기 크기는 2
				shark = { i, j, 2, 0 };
				map[i][j] = EMPTY; // 빈칸으로 바꿔주기!!!!!!!!!!!!!!!!!!!!!!!!!!
			}
		}
	}
}

void init_dist() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) dist[i][j] = INF;
	}
}

void get_dist() {
	init_dist();
	queue<pair<int, int>> q;
	q.push({ shark.y, shark.x });
	dist[shark.y][shark.x] = 0;

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int d = 0; d < 4; d++) {
			int ny = y + dy[d];
			int nx = x + dx[d];
			if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue; // 경계를 벗어나는 경우
			if (shark.s < map[ny][nx]) continue; // 지나갈 수 없는 경우
			if (dist[ny][nx] != INF) continue; // 이미 방문한 경우
			dist[ny][nx] = dist[y][x] + 1;
			q.push({ ny, nx });
		}
	}
}

int move_shark() {
	get_dist(); // 현 상어의 위치에서 갈 수 있는 거리를 구함

	int ny, nx, fish_size, min_dist = INF;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (dist[i][j] == INF || map[i][j] == EMPTY) continue; // 갈 수 없는 곳이거나, 비어 있는 곳인 경우
			if (map[i][j] == shark.s) continue; // 상어와 크기가 같은 경우
			if (dist[i][j] < min_dist) {
				min_dist = dist[i][j];
				fish_size = map[i][j];
				ny = i; nx = j;
			}
		}
	}
	if (min_dist == INF) return 0;

	shark.y = ny; shark.x = nx; shark.cnt++;
	if (shark.cnt == shark.s) { // 자신의 크기와 같은 수의 물고기를 먹을 때 마다 크기가 1 증가
		shark.cnt = 0;
		shark.s++;
	}
	map[ny][nx] = EMPTY;
	return dist[ny][nx];
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	input();
	
	int ans = 0;
	while (1) {
		int res = move_shark();
		if (res == 0) break;
		else ans += res;
	}
	cout << ans;
}