📌문제
📌나의 코드
2164KB, 8ms
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Fish {
int y, x, size;
bool operator<(Fish right) const {
return size > right.size;
}
};
struct EatFish {
int y, x, far;
bool operator<(EatFish right) const {
if (far == right.far) {
if (y == right.y) return x > right.x;
return y > right.y;
}
return far > right.far;
}
};
struct Node {
int y, x, cost;
bool operator<(Node right) const {
return cost > right.cost;
}
};
int n;
int map[21][21];
int dist[21][21];
priority_queue<Fish> fishes;
queue<Fish> canEat;
Fish shark;
int dir[4][2] = { -1, 0, 1, 0, 0, -1, 0, 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) {
shark = { i, j, 2 }; // 처음 크기 2
}
// 물고기들
if (map[i][j] >= 1 && map[i][j] <= 6) {
fishes.push({ i, j, map[i][j] });
}
}
}
}
void dijkstra(int sy, int sx) {
priority_queue<Node> pq;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = 1e9;
}
}
dist[sy][sx] = 0;
pq.push({ sy, sx, 0 });
while (!pq.empty()) {
Node now = pq.top();
pq.pop();
for (int i = 0; i < 4; i++) {
int ny = now.y + dir[i][0];
int nx = now.x + dir[i][1];
if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
if ((map[ny][nx] > shark.size && map[ny][nx] != 9)) continue;
int nextCost = now.cost + 1;
if (dist[ny][nx] <= nextCost) continue;
dist[ny][nx] = nextCost;
pq.push({ ny, nx, nextCost });
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
// 물고기 없으면 바로 종료
if (fishes.empty()) {
cout << 0;
return 0;
}
bool canStart = false;
// 처음부터 이동할 수 있는지 확인
for (int i = 0; i < 4; i++) {
int ny = shark.y + dir[i][0];
int nx = shark.x + dir[i][1];
if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
if (map[ny][nx] > shark.size) continue;
canStart = true;
break;
}
if (!canStart) {
cout << 0;
return 0;
}
int nowTime = 0;
bool flag = true; // 엄마 필요없을 때 true
int cntEat = 0;
while (flag) {
// 1. 아기 상어가 먹을 수 있는 물고기 확인
while (!fishes.empty() && shark.size > fishes.top().size) {
Fish nowFish = fishes.top();
fishes.pop();
// queue에 먹을 수 있는 물고기 넣기
canEat.push(nowFish);
}
// 2. 먹을 수 있는 물고기와 거리 구하기
if (!canEat.empty()) {
dijkstra(shark.y, shark.x);
priority_queue<EatFish> temp;
while (!canEat.empty()) {
Fish nowCanEat = canEat.front();
canEat.pop();
temp.push({ nowCanEat.y, nowCanEat.x, dist[nowCanEat.y][nowCanEat.x] });
}
EatFish nowEat = temp.top();
temp.pop();
// 이동시간이 1초 = 거리만큼 시간 증가
if (nowEat.far == 1e9) continue;
cntEat++;
map[nowEat.y][nowEat.x] = 0;
nowTime += nowEat.far;
shark.y = nowEat.y;
shark.x = nowEat.x;
if (cntEat == shark.size) {
shark.size++;
cntEat = 0;
}
while (!temp.empty()) {
EatFish nowTemp = temp.top();
temp.pop();
// 남은 먹을 수 있는 물고기들을 다시 fishes로 넣어줌
fishes.push({nowTemp.y, nowTemp.x, 0});
}
}
else flag = false;
}
cout << nowTime;
}📌나의 풀이
Fish , EatFish = 구조체
1. 물고기의 위치를 모두 fishes Fish pq에 저장한다.
2. fishes는 물고기 크기가 작은 순으로 정렬 -> fishes top()의 크기가 아기 상어 크기보다 크면 물고기를 먹을 수 없다.
3. 물고기가 없으면 바로 종료한다.
4. 처음에 이동할 수 있는지 확인한다
⇒ 주위에 아기 상어보다 크기가 큰 물고기(3 이상)로 둘러싸였다면 이동을 못한다.
5. 물고기들 중 아기 상어가 먹을 수 있는 물고기를 canEat queue에 저장한다.
6. 먹을 수 있는 물고기가 있다면 아기 상어 위치를 기준으로 dijkstra를 1번 실행한다.
7. temp EatFish pq에 먹을 수 있는 물고기들과의 거리(dijkstra 결과로 나온 dist 배열)를 포함해 저장한다.
8. EatFish 구조체는 우선순위 거리가 가까운 순 > 가장 위에 있는 순(y가 작은 순) > 가장 왼쪽에 있는 순(x가 작은 순) 연산자 오버로딩
9. temp pq top()을 봤을 때 dist 배열이 초기값(1e9)이 아니라면, 즉 갈 수 있는 위치면
- 1) 먹은 물고기(cntEat) 증가
- 2) 해당 위치 map에서 0으로 삭제
- 3) 현재 시간에 먹은 물고기까지의 이동 거리 더하기
- 4) 상어 위치를 먹은 물고기 위치로 갱신
- 5) 상어의 크기만큼 물고기를 먹었으면 크기 1 증가
- 6) 물고기 한 마리만 먹고 남은 물고기는 다시 fishes에 넣기
📌다른 사람 코드
#include <iostream>
#include <queue>
using namespace std;
struct Fish {
int y, x, dist;
};
int n;
int map[21][21];
bool visited[21][21];
int sharkY, sharkX;
int sharkSize = 2;
int ate;
int nowTime;
int dir[4][2] = { -1, 0, 1, 0, 0, -1, 0, 1 };
bool bfs(){
for (int i = 0; i < n; i++){
for (int j = 0; j < n; j++){
visited[i][j] = false;
}
}
int fishY = 0;
int fishX = 0;
int fishDist = 1e9;
queue<Fish> q;
q.push({ sharkY, sharkX, 0 });
visited[sharkY][sharkX] = true;
while (!q.empty()){
Fish now = q.front();
q.pop();
// 현재까지 온 거리가 먹을 수 있는 물고기 위치보다 멀거나 같으면
// 물고기 먹는다
if (now.dist >= fishDist){
sharkY = fishY;
sharkX = fishX;
nowTime += fishDist;
ate++;
if (ate == sharkSize){
ate = 0;
sharkSize++;
}
map[fishY][fishX] = 0;
// 먹었으면 돌아간다
return true;
}
for (int i = 0; i < 4; ++i)
{
int ny = now.y + dir[i][0];
int nx = now.x + dir[i][1];
if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
// 이미 방문한 곳이거나 물고기 크기가 상어 크기보다 더 크면 넘어가기
if (visited[ny][nx] || map[ny][nx] > sharkSize) continue;
visited[ny][nx] = true;
if (map[ny][nx] > 0 && map[ny][nx] < sharkSize) {
// 상어의 다음 위치가 먹을 수 있는 물고기인데,
// 현재까지 저장된 먹을 수 있는 물고기의 위치보다 가까우면 갱신
// 먹을 수 있는 물고기의 가장 가까운 거리를 저장하는 부분
if (fishDist >= now.dist + 1)
{
fishDist = now.dist + 1;
// 먹을 수 있는 물고기의 거리가 같을 때는
// 가장 위에 있는 것, y 값이 작은 것
if (fishY >= ny)
{
// 둘 다 가장 위에 있는 것이라면, y 값이 같으면
if (fishY == ny)
{
// 가장 왼쪽에 있는 것, x 값이 작은 것
if (fishX >= nx)
fishX = nx;
}
// 현재 y 값이 저장된 y보다 작으면
// 현재 먹을 수 있는 물고기가 더 위에 있다면 y, x 둘 다 갱신
else
{
fishY = ny;
fishX = nx;
}
}
}
}
// 현재까지 상어가 이동한 거리 + 1
q.push({ ny, nx, now.dist + 1 });
}
}
return false;
}
int main() {
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) {
sharkY = i;
sharkX = j;
map[i][j] = 0;
}
}
}
while (1) {
// 물고기를 못 먹을 때까지 진행
// 물고기 한 마리 먹으면 돌아온다
if (!bfs()) break;
}
cout << nowTime << "\n";
}✏️개선점
굳이 먹을 수 있는 물고기들을 다 저장해놓을 필요 없이
이동하면서 먹을 수 있으면 그 물고기까지의 거리와 위치를 저장해서
더이상 먹을 물고기가 없을 때까지 한 마리씩 먹으면 된다.
❗ 항상 한 번에 처리하려고 하지 말고, 생각을 더 많이 해서 효율적인 방법을 찾아보자.
공부 기록