문제
풀이 과정
- 아기 상어 크기 조건
- 초기 조건은 2
- 상어 크기보다 물고기가 작을 때 물고기를 먹음
- 먹었다면 카운팅하고 빈칸(0)이 된다
- 카운팅 된 수가 현재 상어 크기와 같다면 상어 크기가 1 커짐
- 상어 크기보다 물고기가 클 때 지나갈 수 없음
- 상어 크기와 물고기 크기가 작거나 같다면 지나갈 수 있음
- 거리가 가까운 물고기가 많을 때 위, 거리가 같은 물고기가 많을 때 왼쪽 순으로 먹는다
예시) 거리가 가까운 물고기가 많을 때
0 0 0 0
0 1 1 0
0 1 9 0
0 0 0 0
상어(9)의 위치: (2,2)
물고기(1)의 위치: (1,1), (1,2), (2,1)
최단 거리 기준
(2,1)과 (1,2)은 거리 1
(1,1)은 거리 2
따라서 가까운 거리 1에서 위쪽 물고기(x 좌표가 작은 물고기)
(1,2)을 먼저 먹음
예시) 거리가 같은 물고기가 많을 때
0 0 0 0 0
0 1 0 1 0
0 0 9 0 0
0 1 0 1 0
0 0 0 0 0
상어(9)의 위치: (2,2)
물고기(1)의 위치: (1,1), (1,3), (3,1), (3,3)
가장 위쪽(작은 x) 선택 → (1,1), (1,3) 중 선택
가장 왼쪽(작은 y) 선택 → (1,1) 선택틀린 코드
- 먹이를 먹을 때마다 bfs를 다시 호출해야 하는데, 먹이 한 번 먹는걸로 생각해가지고 .. 사실 거리가 가까운 물고기가 많을 때 위, 거리가 같은 물고기가 많을 때 왼쪽 순으로 먹는다 이 조건이 이해가 안가서 일반적은 bfs로 일단 질러봤지만 실패했다..ㅎ
#include <stdio.h>
#include <stdlib.h>
#define MAX 21
typedef struct Que {
int x;
int y;
int size;
int dist;
} Q;
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
int n;
int map[MAX][MAX];
int visit[MAX][MAX];
Q que[MAX*MAX];
int front;
int rear;
void enqueue(int x, int y, int size, int dist) {
que[rear].x = x;
que[rear].y = y;
que[rear].size = size;
que[rear].dist = dist;
rear++;
}
Q dequeue() {
return que[front++];
}
int bfs() {
int eat = 0;
int total_dist = 0;
int cur_size = 2;
while (front < rear) {
Q cur = dequeue();
for (int i=0; i<4; i++) {
int nx = cur.x + dx[i];
int ny = cur.y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < n &&
visit[nx][ny] == 0) {
if (map[nx][ny] == 0 || map[nx][ny] == cur.size) {
visit[nx][ny] = 1;
enqueue(nx, ny, cur.size, cur.dist+1);
} else if (map[nx][ny] < cur.size) {
visit[nx][ny] = 1;
map[nx][ny] = 0;
eat++;
if (eat == cur_size) {
eat = 0;
cur_size++;
}
total_dist = cur.dist+1;
enqueue(nx, ny, cur_size, cur.dist+1);
}
}
}
}
return total_dist;
}
int main() {
scanf("%d", &n);
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
scanf("%d", &map[i][j]);
if (map[i][j] == 9) {
visit[i][j] = 1;
enqueue(i, j, 2, 0);
map[i][j] = 0;
}
}
}
int result = bfs();
printf("%d", result);
return 0;
}정답 코드
- 챗gpt 선생님의 말씀에 따라 다시 구성한 코드
- bfs 여러번 호출하여 반복수행하고 매 턴 마다 먹을 물고기를 선택
- 거리를 위쪽과 왼쪽 기준으로 정렬하고 업데이트
- 없으면 result 반환
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX 21
typedef struct Que {
int x, y, size, dist;
} Q;
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};
int n, map[MAX][MAX], visit[MAX][MAX];
Q que[MAX * MAX];
int front, rear;
void enqueue(int x, int y, int size, int dist) {
que[rear].x = x;
que[rear].y = y;
que[rear].size = size;
que[rear].dist = dist;
rear++;
}
Q dequeue() {
return que[front++];
}
int bfs(int *sx, int *sy, int *cur_size) {
front = rear = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
visit[i][j] = 0;
visit[*sx][*sy] = 1;
enqueue(*sx, *sy, *cur_size, 0);
int min_dist = INT_MAX, tx = -1, ty = -1;
while (front < rear) {
Q cur = dequeue();
if (cur.dist > min_dist) break;
for (int i = 0; i < 4; i++) {
int nx = cur.x + dx[i], ny = cur.y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || visit[nx][ny]) continue;
visit[nx][ny] = 1;
if (map[nx][ny] == 0 || map[nx][ny] == *cur_size) {
enqueue(nx, ny, *cur_size, cur.dist + 1);
} else if (map[nx][ny] < *cur_size) {
if (cur.dist + 1 < min_dist) {
min_dist = cur.dist + 1;
tx = nx, ty = ny;
} else if (cur.dist + 1 == min_dist) {
if (nx < tx || (nx == tx && ny < ty)) {
tx = nx, ty = ny;
}
}
}
}
}
if (tx == -1) return 0;
map[tx][ty] = 0;
*sx = tx, *sy = ty;
return min_dist;
}
int solve() {
int sx, sy, cur_size = 2, eat = 0, total_time = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (map[i][j] == 9) sx = i, sy = j, map[i][j] = 0;
while (1) {
int time = bfs(&sx, &sy, &cur_size);
if (!time) break;
total_time += time;
eat++;
if (eat == cur_size) cur_size++, eat = 0;
}
return total_time;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &map[i][j]);
printf("%d\n", solve());
}
Embedded Software Engineer