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

문제 링크

---

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

16236번: 아기 상어

 

접근 방법

---

문제를 읽다가 '거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.부분과 더 큰 물고기는 지나갈 수 없다는 조건에서 BFS 알고리즘의 문제라는 것을 깨닫고, BFS로 문제 풀이를 시작했다. 풀다보니 전형적인 BFS의 형식에 귀찮은 조건이 몇 가지 추가된 꼴이었다.

 

 

소스 코드

---

코드에 주석을 많이 남겨놨습니다. :) 복잡한 계산이 있는 문제가 아니니, 코드로 참고 부탁드려요!

#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 21
#define NUM_DIRECTION 4
using namespace std;
typedef struct coord {
	int y, x, size, time;
};
int N, map[MAX][MAX], visit[MAX][MAX], expp = 0;
coord shark; // 아기 상어의 좌표 및 크기
// vector<coord> fishs; // 물고기들의 좌표 및 크기
vector<coord> eatable_fishs;
const coord direction[NUM_DIRECTION] = { {0, 1, 0, 0}, {0, -1, 0, 0}, {1, 0, 0, 0}, {-1, 0, 0, 0} };

bool comp(const coord& a1, const coord& b1) {
	if (a1.time == b1.time) { // 시간이 동일하다면, y가 작은 순으로
		if (a1.y == b1.y) { // y도 동일하다면 x가 작은 순으로
			return a1.x < b1.x;
		}
		return a1.y < b1.y;
	}
	return a1.time < b1.time; // 시간이 작은 순으로
}

bool isRanged(int y, int x) {
	if (y >= N || x >= N || y < 0 || x < 0) return false;
	return true;
}

void search_eatable() {
	queue<coord> q;
	memset(visit, 0, sizeof(visit)); // 현재 위치에서 시간 계산을 다시 해야하므로 초기화
	eatable_fishs.clear(); // 현재 위치에서 시간 계산을 다시 해야하므로 초기화
	visit[shark.y][shark.x] = 1;
	q.push(shark);
	coord cur;
	int ny, nx;
	while (!q.empty()) {
		cur = q.front();
		q.pop();
		for (int i = 0; i < NUM_DIRECTION; ++i) {
			ny = cur.y + direction[i].y;
			nx = cur.x + direction[i].x;
			if (isRanged(ny, nx) && !visit[ny][nx] && map[ny][nx] <= shark.size) { 
				// 범위 내에 있고, 방문하지 않았으며, 지나가야 하므로 크기가 더 작다면
				if (map[ny][nx] != 0 && shark.size > map[ny][nx])
					// 먹을 수 있는 물고기라면? 물고기 백터에 넣음
					eatable_fishs.push_back({ ny, nx, map[ny][nx], cur.time + 1 });
				visit[ny][nx] = 1;
				q.push({ ny, nx, 0, cur.time + 1 });
			}
		}
	}
}

// 경험치를 체크하여 사이즈와 같아졌다면 사이즈업, 경험치 초기화
void check_exp() {
	if (expp >= shark.size) {
		++shark.size;
		expp = 0;
	}
}

// eatable_fish의 물고기를 먹고, 해당 자리로 이동하며, 소요된 시간을 반환한다.
int move_and_eat(coord eatable_fish) {
	map[shark.y][shark.x] = 0; // 자리를 비운다.
	map[eatable_fish.y][eatable_fish.x] = 9; // 먹어치운 물고기의 좌표로 이동한다.
	shark.y = eatable_fish.y;
	shark.x = eatable_fish.x;
	++expp; // 경험치 +1
	check_exp();
	return eatable_fish.time;
}

int solve() {
	int ret = 0;
	while (1) {
		search_eatable(); // 현재 위치에서 물고기들과의 거리 및 크기 계산
		if (!eatable_fishs.empty()) { // 먹을 수 있는 물고기가 존재한다면
			sort(eatable_fishs.begin(), eatable_fishs.end(), comp); // 좌표 순으로 정렬
			ret += move_and_eat(eatable_fishs.front()); // 가장 가까운 물고기를 먹는다.
		}
		else // 먹을 수 있는 물고기가 존재하지 않는다면
			break;
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	memset(visit, 0, sizeof(visit));
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> map[i][j];
			if (map[i][j] != 0) { // 빈 칸이 아니라면
				if (map[i][j] == 9) { // 아기 상어라면
					shark.y = i;
					shark.x = j;
					shark.size = 2; // 초기 크기 = 2(조건)
					shark.time = 0;
				}
			}
		}
	}
	cout << solve();
	return 0;
}

개발 환경은 VS2019입니다.

질문, 지적, 덧글 환영합니다!