반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. bfs


이 문제는 조건만 잘 생각하면 쉽게 해결 할 수 있다.


1. 상어는 자신보다 작거나 같은 크기의 상어가 있는 곳을 움직 일 수 있다.

2. 상어는 자신보다 작은 것만 먹을 수 있다.

3. 상어는 아래 정렬조건을 가진다.

- 거리가 가장 가까운 물고기를 먹으러 간다.

- 거리가 가까운 물고기가 많다면, 가장 위에 있는 물고기, 그러한 물고기가 여러마리라면, 가장 왼쪽에 있는 물고기를 먹는다.



사실 정렬은 pair를 이용하여 거리,y좌표,x좌표를 담고 sort를 하면 알아서 정렬되도록 조건이 되어있다.


자신이 먹을 수 있는 상어를 모두 shark 벡터에 담고 정렬 한 후 벡터가 비어있다면 INF를 리턴, 그 외에는 벡터 첫번째 값을 리턴한다.


그리고 BFS의 리턴값이 INF라면 엄마 상어를 부르면 되고(종료)


BFS값이 존재한다면 그게 최단 거리에 있는 먹을 수 있는 상어를 의미하므로 먹이고 다음 BFS를 진행하면 된다.




소스 코드 : 


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
#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <memory.h>
 
#define INF 987654321
using namespace std;
 
typedef pair<intint> pii;
 
int arr[22][22];
int dy[4= { -1,0,0,};
int dx[4= { 0,-1,1,};
bool visit[22][22];
 
int n;
int sy, sx, sSize = 2, eat;
int ans;
 
pair<pii, pii> bfs() {
    memset(visit, 0sizeof(visit));
 
    queue<pair<pii, int> > q;
    q.push({ {sy,sx}, });
 
    vector<pair<int, pii>> shark;
 
    while (!q.empty()) {
        int y = q.front().first.first;
        int x = q.front().first.second;
        int dist = q.front().second;
        q.pop();
 
        if (arr[y][x] != && arr[y][x] < sSize) 
            shark.push_back({ dist,{ y,x } });
 
        if (visit[y][x])
            continue;
 
        visit[y][x] = true;
 
        for (int i = 0; i < 4; i++) {
            int ny = dy[i] + y;
            int nx = dx[i] + x;
 
            if ((<= ny && ny < n) && (<= nx && nx < n) && arr[ny][nx] <= sSize)
                q.push({ {ny,nx}, dist + });
        }
    }
 
    if(shark.empty())
        return{ { INF, INF } , { INF, INF } };
 
    sort(shark.begin(), shark.end());
    
    int dist = shark[0].first;
    int y = shark[0].second.first;
    int x = shark[0].second.second;
    int size = arr[y][x];
    return{ {y,x},{dist,size} };
}
 
int main() {
    scanf("%d"&n);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            scanf("%d"&arr[i][j]);
            if (arr[i][j] == 9)
                sy = i, sx = j, arr[i][j] = 0;
        }
 
    while (1) {
        pair<pii, pii> tmp = bfs();
        if (tmp.second.first == INF)
            break;
 
        int y = tmp.first.first;
        int x = tmp.first.second;
        int dist = tmp.second.first;
        int size = tmp.second.second;
 
        ans += dist;
 
        sy = y;
        sx = x;
        eat++;
        arr[y][x] = 0;
        if (eat == sSize) 
            sSize++, eat = 0;
    }
 
    printf("%d\n", ans);
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus

반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[16234번] 인구 이동  (4) 2018.10.22
[16235번] 나무 재테크  (0) 2018.10.22
[14890번] 경사로  (0) 2018.09.27
[1038번] 감소하는 수  (0) 2018.09.25
[16159번] 전광판의 숫자  (0) 2018.09.22