[BOJ][삼성기출] 16236. 아기 상어
문제 접근
- 먹을 수 있는 물고기 탐색이 포인트이다. (get_target())
- 우선 모든 물고기에 대해 상어와의 거리를 구한다.
- 그 다음 먹을 수 있는 물고기가 있다면 물고기의 정보를 반환한다.
우선 모든 물고기의 거리를 -1로 세팅한다.
bfs를 통해 도달 가능한 물고기의 거리를 update한다.
만일, update 후에도 모든 물고기의 상어와의 거리가 -1이면 먹을 수 있는 물고기가 없는 것이므로 -1을 반환한다. (먹을 수 있는 물고기가 있는지 여부 탐색 방법)
거리가 -1이 아닌 물고기가 한 마리 이상 있다면 거리가 최소 거리에 위치한 물고기를 먹는다.
최소 거리에 위치한 물고기가 여러 마리라면, vector에서 가장 첫 번째로 탐색되는 물고기가 문제에서 정의하는 우선순위에 부합하게 된다. (입력 시 차례대로 vector에 넣었으며, 입력은 왼쪽 위부터 시작됐기 때문이다.)
- 다른 사람들의 풀이를 보니 food 구조체에 life 변수를 쓰지 않았다. (과거의 나 또한)
그래도 문제를 풀 때 내가 세운 논리는 정리되었다.
다음에 리뷰를 해보면 좋을 것 같다.
풀이
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef struct food {
int x;
int y;
int size;
int d;
bool life;
} food;
int N, M, rst, cnt, sx, sy, s_size;
int map[20][20];
vector <food> F;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
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] > 0 && map[i][j] < 9) {
food f;
f.x = i; f.y = j; f.size = map[i][j]; f.d = 0; f.life = true;
F.push_back(f);
}
else if (map[i][j] == 9) {
sx = i; sy = j; s_size = 2;
}
}
}
rst = 0; cnt = 0;
}
void get_target(int ret) {
rst += F[ret].d;
map[sx][sy] = 0;
sx = F[ret].x;
sy = F[ret].y;
F[ret].life = false;
map[F[ret].x][F[ret].y] = 9;
cnt++;
if (s_size == cnt) {
s_size++;
cnt = 0;
}
}
int is_range(int x, int y) {
if (x >= 0 && x < N && y >= 0 && y < N) return true;
return false;
}
int find_target() {
int is_visit[20][20];
memset(is_visit, 0, sizeof(is_visit));
queue <pair<pair<int, int>, int>> Q;
Q.push(make_pair(make_pair(sx, sy), 0));
is_visit[sx][sy] = 1;
for (int i = 0; i < F.size(); i++) {
F[i].d = -1;
}
// 1. 모든 먹을 수 있는 물고기에 대해 상어와의 거리를 구한다.
while (!Q.empty()) {
int cx = Q.front().first.first;
int cy = Q.front().first.second;
int d = Q.front().second;
Q.pop();
// 현재 위치에 물고기가 있는지 확인
for (int i = 0; i < F.size(); i++) {
if (map[cx][cy] && cx == F[i].x && cy == F[i].y) {
if (map[cx][cy] < s_size) {
F[i].d = d;
break;
}
}
}
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
if (!is_visit[nx][ny] && is_range(nx, ny) && map[nx][ny] <= s_size) {
is_visit[nx][ny] = 1;
Q.push(make_pair(make_pair(nx, ny), d + 1));
}
}
}
// 2. 살아 있는 물고기 중 먹을 수 있는 물고기가 한 마리 이상 있는가?
bool flag = false;
for (int i = 0; i < F.size(); i++) {
if (F[i].life && F[i].d != -1) flag = true;
}
if (!flag) return -1; // 없다면 종료
//있다면 min distance를 구하고 min distance에 해당하는 물고기 중 가장 왼쪽에 위치한 물고기
int m = 100000;
for (int i = 0; i < F.size(); i++) {
if (F[i].life && F[i].d != -1) m = min(m, F[i].d);
}
for (int i = 0; i < F.size(); i++) {
if (F[i].life && F[i].d != -1) {
if (F[i].d == m) return i;
}
}
}
void solve() {
while(true) {
int ret = find_target();
if (ret == -1) {
break;
}
get_target(ret);
}
}
int main() {
input();
solve();
cout << rst << endl;
}
Author And Source
이 문제에 관하여([BOJ][삼성기출] 16236. 아기 상어), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kyoung99u/BOJ-16236-아기-상어저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)