문제 링크
💡 너비 우선 탐색/그래프 이론/그래프 탐색/구현/시뮬레이션
Memory 2028KB Time 160ms Code Length 2526B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
| #include<iostream>
#include<math.h>
#include<cstring>
#include<queue>
using namespace std;
int N;
int Map[20][20];
struct info {
int y, x;
};
info baby_shark, target;
int min_dist = 1e9;
int shark_size = 2;
int get_fish = 0;
void init() {
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) {
baby_shark.y = i;
baby_shark.x = j;
}
}
}
}
int find_dist(int y, int x) { // 상어와 물고기의 최단 거리 구하기.
// 상어가 큰 물고기를 피해서 이동하는 최단 거리를 구해야 한다.
const int dy[] = { 1, 0, -1, 0 };
const int dx[] = { 0,-1, 0, 1 };
queue<info> q;
int visited[20][20];
memset(visited, 0, sizeof(visited));
q.push({ baby_shark.y, baby_shark.x });
visited[baby_shark.y][baby_shark.x] = 1;
while (!q.empty()) {
info now = q.front(); q.pop();
if (now.y == y && now.x == x) { // 해당 물고기 위치에 도달
return visited[now.y][now.x] - 1;
}
for (int i = 0; i < 4; i++) {
int ny = now.y + dy[i];
int nx = now.x + dx[i];
if (ny >= N || nx >= N || ny < 0 || nx < 0) continue;
if (visited[ny][nx] != 0) continue;
if (Map[ny][nx] > shark_size) continue; // 큰 물고기 피해가기
visited[ny][nx] = visited[now.y][now.x] + 1;
q.push({ ny,nx });
}
}
return 1e9; // 도달 하지 못했으므로 매우 큰값 반환
}
bool findFish() {
bool flag = false;
min_dist = 1e9;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (Map[i][j] < shark_size && Map[i][j] > 0 && Map[i][j] != 9) { // 물고기 크기가 작고 거리가 최소일때
// 최단 거리 구하기.
int dist = find_dist(i, j);
if (min_dist > dist) {
flag = true;
min_dist = dist;
target.y = i;
target.x = j;
}
}
}
}
return flag;
}
void eat_fish() {
Map[baby_shark.y][baby_shark.x] = 0; // 현재 위치 비움
Map[target.y][target.x] = 9; // 물고기 위치가 상어 위치가됨.
baby_shark.y = target.y;
baby_shark.x = target.x;
get_fish++; // 먹은 물고기 수 증가
if (get_fish == shark_size) { // 상어가 먹은 물고기가 조건에 부합할 시 크기 성장.
shark_size++;
get_fish = 0;
}
}
void printmap() { // 디버깅용
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << Map[i][j] << " ";
}
cout << endl;
}
}
int main() {
init();
int cnt = 0;
while (1) {
if (!findFish()) { // 물고기 찾기
break;
}
eat_fish();
cnt += min_dist;
}
cout << cnt;
}
|
이 코드는 N x N 크기의 맵에서 상어가 먹을 수 있는 물고기를 찾아 먹는 프로그램이다.
init 함수에서 맵을 초기화하고 상어의 위치를 찾는다.
find_dist 함수는 상어와 물고기 사이의 최단 거리를 구하는 함수이다.
findFish 함수는 상어가 먹을 수 있는 물고기를 찾고, 그 중 최단 거리에 있는 물고기를 선택한다.
eat_fish 함수는 선택된 물고기를 먹는다. 상어의 위치를 업데이트하고, 먹은 물고기 수가 상어 크기와 같아지면 상어 크기를 키운다.
main 함수에서는 물고기를 찾아 먹는 과정을 반복하며 걸린 시간을 출력한다.
Behind..
처음에 이 문제를 풀 때 **자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없다!!** 라는 조건을 보지 못했고 아래와 같이 코딩을 했다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
| #include<iostream>
#include<math.h>
using namespace std;
int N;
int Map[20][20];
struct info {
int y, x;
};
info baby_shark, target;
int min_dist = 1e9;
int shark_size = 2;
int get_fish = 0;
void init() {
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) {
baby_shark.y = i;
baby_shark.x = j;
}
}
}
}
bool findFish() {
bool flag = false;
min_dist = 1e9;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (Map[i][j] < shark_size && Map[i][j] > 0) { // 물고기 크기가 작고 거리가 최소일때
flag = true;
int dist = abs(baby_shark.y - i) + abs(baby_shark.x - j);
if (min_dist > dist) {
min_dist = dist;
target.y = i;
target.x = j;
}
}
}
}
return flag;
}
void eat_fish() {
Map[baby_shark.y][baby_shark.x] = 0; // 현재 위치 비움
Map[target.y][target.x] = 9; // 물고기 위치가 상어 위치가됨.
baby_shark.y = target.y;
baby_shark.x = target.x;
get_fish++; // 먹은 물고기 수 증가
if (get_fish == shark_size) { // 상어가 먹은 물고기가 조건에 부합할 시 크기 성장.
shark_size++;
get_fish = 0;
}
}
void printmap() { // 디버깅용
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << Map[i][j] << " ";
}
cout << endl;
}
}
int main() {
init();
int cnt = 0;
while (1) {
if (!findFish()) { // 물고기 찾기
break;
}
eat_fish();
cnt += min_dist;
}
printf("%d\n", cnt);
}
|
<반례>
```c++
6
6 0 6 0 6 1
0 0 0 0 0 2
2 3 4 5 6 6
0 0 0 0 0 2
0 2 0 0 0 0
3 9 3 0 0 1
```
그래서 BFS를 이용해서 각 상어까지 도달하는데 걸리는 거리를 계산하는 함수를 추가하였다.
```c++
#include
#include
#include
#include
using namespace std;
int N;
int Map[20][20];
struct info {
int y, x;
};
info baby_shark, target;
int min_dist = 1e9;
int shark_size = 2;
int get_fish = 0;
void init() {
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) {
baby_shark.y = i;
baby_shark.x = j;
}
}
}
}
int find_dist(int y, int x) { // 상어와 물고기의 최단 거리 구하기.
// 상어가 큰 물고기를 피해서 이동하는 최단 거리를 구해야 한다.
const int dy[] = { 1, 0, -1, 0 };
const int dx[] = { 0,-1, 0, 1 };
queue q;
int visited[20][20];
memset(visited, 0, sizeof(visited));
q.push({ baby_shark.y, baby_shark.x });
visited[baby_shark.y][baby_shark.x] = 1;
while (!q.empty()) {
info now = q.front(); q.pop();
if (now.y == y && now.x == x) { // 해당 물고기 위치에 도달
return visited[now.y][now.x]-1;
}
for (int i = 0; i < 4; i++) {
int ny = now.y + dy[i];
int nx = now.x + dx[i];
if (ny >= N || nx >= N || ny < 0 || nx < 0) continue;
if (visited[ny][nx] != 0) continue;
if (Map[ny][nx] > shark_size) continue; // 큰 물고기 피해가기
visited[ny][nx] = visited[now.y][now.x] + 1;
q.push({ ny,nx });
}
}
return 1e9; // 도달 하지 못했으므로 매우 큰값 반환
}
bool findFish() {
bool flag = false;
min_dist = 1e9;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (Map[i][j] < shark_size && Map[i][j] > 0) { // 물고기 크기가 작고 거리가 최소일때
// 최단 거리 구하기.
int dist = find_dist(i, j);
if (min_dist > dist) {
flag = true;
min_dist = dist;
target.y = i;
target.x = j;
}
}
}
}
return flag;
}
void eat_fish() {
Map[baby_shark.y][baby_shark.x] = 0; // 현재 위치 비움
Map[target.y][target.x] = 9; // 물고기 위치가 상어 위치가됨.
baby_shark.y = target.y;
baby_shark.x = target.x;
get_fish++; // 먹은 물고기 수 증가
if (get_fish == shark_size) { // 상어가 먹은 물고기가 조건에 부합할 시 크기 성장.
shark_size++;
get_fish = 0;
}
}
void printmap() { // 디버깅용
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << Map[i][j] << " ";
}
cout << endl;
}
}
int main() {
init();
int cnt = 0;
while (1) {
if (!findFish()) { // 물고기 찾기
break;
}
eat_fish();
cnt += min_dist;
}
cout << cnt;
}
```
결국 최종적으로 수정한 코드가 맨 위에 있는 코드이다..
이 문제를 푼 것에 만족을 했지만
다른 코드들을 확인해 보니 시간을 훨씬 더 줄일 수 있는 방법이 있었다.
바로, 물고기들의 위치를 모든 배열을 돌며 일일이 먹을 수 있는 물고기를 찾은 후 물고기와 상어의 거리를 각각 측정해 최솟값을 찾는 것이 아닌, 상어의 위치에서 bfs로 주변을 탐색하고, 탐색된 것이 먹을 수 있는 물고기라면 해당 물고기에 대한 데이터를 찾는 방법을 쓰면 좀 더 시간을 줄일 수 있었다.
이때 먹을 수 있는 물고기가 여러 마리라면 맨 위, 그리고 맨 왼쪽에 있는 물고기 순서로 우선순위를 가지므로, Priority Queue를 이용한 BFS를 작성할 수 있다.
```c++
#define _CRT_SECURE_NO_WARNINGS
#include
#include
using namespace std;
int n;
int map[21][21];
struct Shark {
int y, x, size;
int eat; // 지금까지 먹은 물고기 개수
};
struct Fish {
int y, x, lev;
};
Shark shark;
int dy[4] = { -1,0,0,1 };
int dx[4] = { 0,-1,1,0 };
struct Compare {
bool operator() ( Fish f, Fish tar ) {
if (tar.lev < f.lev) return true;
else if (tar.lev > f.lev) return false;
if (tar.y < f.y) return true;
else if (tar.y > f.y) return false;
return tar.x < f.x;
}
};
Fish bfs() {
Fish f = { -1,-1,-1 };
priority_queue<Fish, vector, Compare> q;
int visited[21][21] = { 0, };
q.push({ shark.y, shark.x });
visited[shark.y][shark.x] = 1;
while (!q.empty()) {
Fish now = q.top();
q.pop();
if (1 <= map[now.y][now.x] && map[now.y][now.x] < shark.size) return now;
for (int i = 0; i < 4; i++) {
int ny = now.y + dy[i];
int nx = now.x + dx[i];
if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
if (visited[ny][nx] || map[ny][nx] > shark.size) continue;
q.push({ ny,nx,now.lev + 1 });
visited[ny][nx] = 1;
}
}
return f;
}
int solve() {
int t = 0;
while (1) {
// 1. bfs
Fish ret = bfs();
if (ret.y == -1) return t;
// 2. 물고기 먹기
map[ret.y][ret.x] = 0;
shark.y = ret.y, shark.x = ret.x;
if (++shark.eat == shark.size) {
shark.size++;
shark.eat = 0;
}
t += ret.lev;
}
return t;
}
int main() {
//freopen("input.txt", "r", stdin);
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) {
map[i][j] = 0;
shark = { i,j,2,0 };
}
}
}
int ans = solve();
printf("%d\n", ans);
return 0;
}
```
---
2024-8-21일 다시 이 문제를 풀어 보았다.
조금 오래 걸리긴 했지만 빡구현 문제라 그리 어렵진 않았던 것 같다.
> **Memory 2028KB Time 156ms Code Length 2059B**
```c++
#include
#include
using namespace std;
int N;
int map[20][20];
struct shark_info {
int y, x, ate, size;
};
struct target_info {
int y, x, dist;
};
struct queue_info {
int y, x, dist;
};
shark_info shark;
target_info fish;
int dist = 0;
void init() {
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.y = i;
shark.x = j;
shark.ate = 0;
shark.size = 2;
}
}
}
}
int bfs(int target_y, int target_x) {
const int dy[] = {-1,1,0,0};
const int dx[] = {0,0,-1,1};
int dist = 1e9;
int visited[20][20] = { 0 };
queue q;
q.push({ shark.y,shark.x,0 });
while (!q.empty()) {
queue_info now = q.front(); q.pop();
if (now.y == target_y && now.x == target_x) {
dist = now.dist;
break;
}
for (int i = 0; i < 4; i++) {
int ny = now.y + dy[i];
int nx = now.x + dx[i];
if (ny >= N || nx >= N || ny < 0 || nx < 0) continue;
if (map[ny][nx] > shark.size) continue;
if (visited[ny][nx] == 1) continue;
visited[ny][nx] = 1;
q.push({ ny,nx,now.dist + 1 });
}
}
return dist;
}
bool find_fish() { // 경로상 먹을 수 있는 물고기 찾기 (fish data 최신화)
int minV = 1e9;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] != 0 && map[i][j] != 9 && map[i][j] < shark.size) {
int dist = bfs(i, j);
if (dist < minV) { // 최솟값 갱신
minV = dist;
fish.y = i;
fish.x = j;
fish.dist = minV;
}
}
}
}
if (minV == 1e9) {
return false;
}
else {
return true;
}
}
void eat_fish() {
// 맵 최신화
map[shark.y][shark.x] = 0;
map[fish.y][fish.x] = 9;
// shark 위치 이동
shark.y = fish.y;
shark.x = fish.x;
shark.ate++;
if (shark.ate == shark.size) { // 상어 크기 반영
shark.ate = 0;
shark.size++;
}
}
int main() {
init();
int T =0;
while (1) {
if (!find_fish()) { // 먹을수 있는 물고기 존재 x
break;
}
eat_fish();
T += fish.dist;
}
cout << T;
}
```
이 코드는 N x N 크기의 맵에서 상어가 먹을 수 있는 물고기를 찾아가며 먹는 과정을 시뮬레이션하는 프로그램이다.
init() 함수에서 맵의 크기(N)와 각 칸의 정보를 입력받고, 상어의 초기 위치와 크기를 설정한다.
bfs() 함수는 상어의 위치부터 목표 지점까지의 최단 거리를 계산하는 함수이다. 너비 우선 탐색을 이용하여 최단 거리를 구한다.
find_fish() 함수는 상어가 먹을 수 있는 물고기를 찾아서 그 물고기까지의 최단 거리를 구하는 함수이다. 이때, 상어의 크기보다 작은 물고기를 찾아야 하며, 최단 거리를 가진 물고기를 찾아 fish 구조체에 저장한다.
eat_fish() 함수는 먹을 물고기가 정해지면 해당 물고기를 먹고 상어의 위치와 크기를 업데이트하는 함수이다.
main() 함수에서는 init() 함수를 호출하여 초기화를 수행하고, find_fish() 함수를 통해 먹을 수 있는 물고기를 찾아가며 eat_fish() 함수를 호출하여 물고기를 먹는 과정을 반복한다. 이를 통해 총 소요된 시간(T)을 계산하여 출력한다.
